Problem Description

There is a piece of land with dimensions $r \times s$, and Matej wants to buy it. Each $1\times1$ square on this land has a different price.

Given a non-empty submatrix with a total price of $m$, the weight of this submatrix is defined as $|m-a|+|m-b|$. You need to find the submatrix with the minimum weight.

You only need to output the minimum weight.

Input Format

The first line contains four positive integers $r$, $s$, $a$, and $b$.

The following $r$ lines, each containing $s$ positive integers, represent the prices of the land. The $j$-th number in the $i$-th line is $c_{i,j}$, indicating the price.

Output Format

Output a single integer $v$, which represents the minimum weight of a non-empty submatrix.

Sample Input and Output

Sample Input #1

2 2 10 10
1 3
4 1

Sample Output #1

2

Sample Input #2

3 2 3 4
1 9
1 1
8 1

Sample Output #2

3

Sample Input #3

3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7

Sample Output #3

2

Notes

Sample Explanation 2

As shown in the image, the total price is $1 + 1 = 2$, and the weight of this land is $|3−2| + |4−2| = 3$.

Data Range

For $14\%$ of the data: $1 \le r, s \le 20$

For $28\%$ of the data: $1 \le r, s \le 100$

For $100\%$ of the data: $1 \le r, s \le 500$, $1 \le a, b, c_{i,j} \le 10^9$

This problem has the same scoring as in COCI 2021-2022#6, with a maximum score of $70$ points.

见题面 Input 部分

见题面 Output 部分