Page not loading? Try clicking here.
Placeholder

#7052

Zemljište 2s 1024MB

Problems

Matej is, as is well known, the biggest Croatian innovator and businessman. His company is expanding, which is why he decided to buy a plot of land near Velika Gorica. The available land is a rectangle-shaped region consisting of r × s square unit cells. Each cell has its own price and it’s not possible to purchase only a part of a cell. Matej is an experienced businessman and he knows that the key to success is not simply to buy the biggest plot of land or the least expensive one. Instead, he should buy a plot of land whose price is as close as possible to the magic numbers given to him by Milan the psychic.

At the beginning of his career, Milan revealed to Matej two magic numbers a and b crucial for commercial success. Therefore, Matej wishes to buy a (nonempty) rectangular plot of land so that the distance between its price and the magic numbers is as small as possible. The distance between the price and a single magic number is just the absolute value of their difference, and the distance between the price and both of the magic numbers is the sum of these absolute differences. Help Matej and determine the minimum possible distance between the price of the plot of land and the two magic numbers.


Input

The first line contains positive integers r, s, a and b (1 ≤ r, s ≤ 500, 1 ≤ a, b ≤ 10^9) from the problem.

The i-th of the following r lines contains a sequence of s positive integers c_{ij} (1 ≤ c_{ij} ≤ 10^9), the prices of the individual cells, in order.


Output

In the only line print the minimum possible distance between the price of the plot of land and the two magic numbers.


Subtask

# Score Condition
#125

1\leq r, s\leq 20

#226

1\leq r, s\leq 100

#349

No additional constraints.


Example #1

2 2 10 10
1 3
4 1
2

Example #2

3 2 3 4
1 9
1 1
8 1
3

Matej can buy a plot of land consisting of two adjacent cells of cost 1. The total price is then 1 + 1 = 2, and the distance between it and the magic numbers is |3 − 2| + |4 − 2| = 3.


Example #3

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


Source

COCI 2021/2022 Contest #6

You must sign in to write code.