COCI '21 Contest 6 #2 Zemljište

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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 \times 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 determine the minimum possible distance between the price of the plot of land and the two magic numbers.

Input Specification

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

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

Output Specification

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

Constraints

Subtask Points Constraints
1 10 1 \le r, s \le 20
2 20 1 \le r, s \le 100
3 40 No additional constraints.

Sample Input 1

2 2 10 10
1 3
4 1

Sample Output 1

2

Sample Input 2

3 2 3 4
1 9
1 1
8 1

Sample Output 2

3

Explanation for Sample Output 2

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.

Sample Input 3

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

Sample Output 3

2

Comments

There are no comments at the moment.