Land Purchase

Interview

Time limit2sMemory limit512 MB

Summary

Given an r by s grid of cell prices and two numbers a and b, find the nonempty rectangle whose total price minimizes |x-a| + |x-b|.

Level: Medium6 of 10
Topics: Prefix sum, Two pointers, Matrix
Solved: No attempts yet

Problem

Matej is the biggest innovator and businessman in Croatia. His company is expanding, so he wants to buy a plot of land near Velika Gorica. The land is a rectangle of $r \times s$ unit cells. Each cell has its own price, and a cell cannot be bought in part. Matej wants the price of his plot to be as close as possible to two magic numbers $a$ and $b$ given by Milan the psychic. The distance between a price and one magic number is the absolute value of their difference. The distance between a price and both magic numbers is the sum of these two absolute differences. Find the minimum possible distance for a nonempty rectangular plot.

Input

The first line contains positive integers $r$ , $s$ , $a$ and $b$ ( $1 \le r, s \le 500$ , $1 \le a, b \le 10^9$ ).

The $i$ -th of the following $r$ lines contains $s$ positive integers $c_{ij}$ ( $1 \le c_{ij} \le 10^9$ ), the prices of the cells in that row, in order.

Output

Print the minimum possible distance between the price of the plot and the two magic numbers.

Hint

In the second sample, Matej can buy a plot of two adjacent cells, each costing $1$ . The total price is $1 + 1 = 2$ , and its distance to the magic numbers is $|3 - 2| + |4 - 2| = 3$ .

Examples3

Example 1
Input
```
2 2 10 10
1 3
4 1
```
Expected output
```
2
```
Example 2
Input
```
3 2 3 4
1 9
1 1
8 1
```
Expected output
```
3
```
Example 3
Input
```
3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
```
Expected output
```
2
```