Problem Description

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

Let the sum of prices in a non-empty submatrix be $m$. Then the value (weight) of this submatrix is $|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$.

In the following $r$ lines, the $i$-th line contains $s$ positive integers. The $j$-th number is $c_{i,j}$, which represents the price.

Output Format

Output one integer $v$ in a single line, which denotes the minimum weight among all non-empty submatrices.

2 2 10 10
1 3
4 1

2

3 2 3 4
1 9
1 1
8 1

3

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

2

Hint

Sample Explanation 2

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

Constraints

For $14\%$ of the testdata: $1\le r,s\le20$.

For $28\%$ of the testdata: $1\le r,s\le100$.

For $100\%$ of the testdata: $1\le r,s\le500$, $1\le a,b,c_{i,j}\le10^9$.

The score distribution of this problem is the same as COCI 2021-2022#6, with a full score of $70$ points.

Translated by ChatGPT 5