시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4 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개의 정수로 이미지가 주어진다.

출력

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

예제 입력

2 2 0 10
3 7
6 2

예제 출력

18

힌트