시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 0 0 0.000%

문제

회색조로 표현되는 이미지가 있다. 각 칸의 색깔은 0부터 255까지의 정수로 표현된다. 이러한 이미지를 흑백으로 근사시키려 한다. 이때 원래 그림과의 비슷한 정도를 나타내는 값이 이러한 근사 이미지의 에너지가 된다. 근사 이미지의 에너지는 다음과 같이 계산된다.

  1. 어떤 칸의 색깔이 X일 때, 그 칸을 흑색으로 근사시키면 에너지가 |X - A|가 된다.
  2. 어떤 칸의 색깔이 X일 때, 그 칸을 백색으로 근사시키면 에너지가 |X - B|가 된다.
  3. 어떤 칸의 색깔이 X이고, 그에 인접한 칸의 색깔이 Y이고, 두 칸을 서로 다른 색으로 근사시키면 에너지가 |X-Y|가 된다.

근사 이미지의 에너지는 이러한 에너지들의 총 합이 된다. 여기서 A, B(0≤A, B≤255)는 입력으로 주어지는 상수이다. 예를 들어 아래와 같은 2×2 크기의 이미지를 근사시킨 경우를 살펴보자. A=0, B=10이다.

3 (흑) 7 (백)
6 (백) 2 (흑)

이 경우, 우선 각 칸에 대해서 3+3+4+2의 에너지가 나오고, 인접해있는 칸들에 의해서 4+3+5+4의 에너지가 나온다. 따라서 이때의 에너지는 28이 된다. 하지만 모두 흑색으로 할 경우에는 18이 되고 이 경우가 최소의 에너지가 된다.

이미지가 주어졌을 때, 최소의 에너지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 네 정수 n, m(1≤n, m≤20), A, B가 주어진다. 다음 n개의 줄에는 m개의 정수로 이미지가 주어진다.

출력

첫째 줄에 최소 에너지를 출력한다.

예제 입력 1

2 2 0 10
3 7
6 2

예제 출력 1

18