Minimum Weight Submatrix

Given a matrix of dimensions $r \times s$ where each $1 \times 1$ cell has a unique cost, you are to determine a non-empty submatrix (i.e. a contiguous rectangular block) that minimizes its weight. For a submatrix with a total price sum $m$, its weight is defined as

where $a$ and $b$ are given integers. Output the minimum weight possible among all submatrices.

inputFormat

The first line of the input contains four integers $r$, $s$, $a$, and $b$ ($1 \le r, s \le 300$, $-10^9 \le a, b \le 10^9$). Each of the next $r$ lines contains $s$ space-separated integers, representing the price of each $1 \times 1$ cell in the matrix. All prices are distinct and lie within the range $[-10^9, 10^9]$.

outputFormat

Output a single integer—the minimum weight, as defined by $$|m - a| + |m - b|,$$ where $m$ is the sum of the prices in the chosen submatrix.

sample

1 1 3 5
10

12