Image Energy

A grayscale image consists of n×m cells, and each cell has an integer value from 0 to 255. You will approximate each cell as either black or white. The energy of an approximated image is the sum of the following values.

1. If a cell with value X is approximated as black, |X - A| is added.
2. If a cell with value X is approximated as white, |X - B| is added.
3. For two side-adjacent cells with original values X and Y, if the two cells are approximated with different colors, |X - Y| is added.

Given the constants A and B, find the minimum possible energy over all choices of colors for the cells.

The first line contains four integers n, m, A, and B. The constraints are 1 ≤ n, m ≤ 20 and 0 ≤ A, B ≤ 255.

Each of the next n lines contains m integers describing one row of the image. Each value is between 0 and 255, inclusive.

Print the minimum possible energy.