P8343 [COCI 2021/2022 #6] Zemljište

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.

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 one integer $v$ in a single line, which denotes the minimum weight among all non-empty submatrices.

### 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](https://hsin.hr/coci/contest6_tasks.pdf), with a full score of $70$ points. Translated by ChatGPT 5