N. The Volcano And the Dragon Egg
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A member of the Warlocks of Qarth named Kovarro Khalil stumbled upon a rare opportunity while exploring the Freehold of Valyria. He discovered inside a volcano pit a dragon egg laying on a safe island of rock surrounded from all direction by magma.

Overjoyed with his finding the mage started casting a telekinesis spell to bring the egg to him, but unfortunately, the volcano suddenly became active and the magma level started rising at a rate of $$$1mm$$$ per millisecond.

The magma stocked inside the volcano is infinite and it will keep rising at the same rate until it reaches the dragon egg.

The warlock is aware that if the magma touches the egg, it may hatch and the telekinesis spell will be ineffective.

Given a bird eye view detailing the topology of the volcano pit and the position of the dragon egg, help the warlock determine how much time he still has before the magma touch the dragon egg.

The topology of the volcano pit will be represented by $$$n \times m$$$ grid where each cell indicate the elevation of that particular point above the magma level in mm (cells containing $$$0$$$ represents the magma level at the time when the warlock started casting his spell)

notice that the egg can be placed in any altitude on top of the rocky island and it may be surrounded by a wall of rock in this case the only way that the magma reach the egg is when the magma level goes over the wall of rock.

Due to the magical properties of the rocky island, the rock won't melt when touched by magma.

Input

The first line contains 2 integer $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^3)$$$ respectively the length and width of the provided view of the volcano pit.

The second line contains 2 integer $$$x$$$ $$$(2 \le x \le n-1)$$$ and $$$y$$$ $$$(2 \le y \le m-1)$$$ the coordinates of the rock on top of which the dragon egg is placed.

Then a grid of $$$n \times m$$$ numbers will follow representing the topology of the volcano pit at the time when the warlock started casting his spell $$$(0 \le a[i][j] \le 10^9)$$$

Each number represent the elevation of that point above the magma level while $$$0$$$ represents points already swallowed by magma

It is guaranteed that the outer layer of the volcano pit contains only lava.

Output

Help the warlock determine how much time he still has before the magma touch the dragon egg.

Examples
Input
5 5
3 3
0 0 0 0 0
0 0 2 0 0
0 2 1 2 0
0 0 2 0 0
0 0 0 0 0
Output
3
Input
3 4
2 2
0 0 0 0
0 1 0 0
0 0 0 0
Output
2
Input
5 5
3 3
0 0 0 0 0
0 2 2 1 0
0 2 3 1 0
0 2 2 1 0
0 0 0 0 0
Output
4
Input
7 7
4 4
0 0 0 0 0 0 0
0 0 2 2 0 0 0
0 0 3 3 2 0 0
0 3 3 2 5 1 0
0 4 1 3 3 1 0
0 0 2 2 0 0 0
0 0 0 0 0 0 0
Output
4
Note

Below is a simulation of the 4th test example

The answer is $$$4$$$ since after exactly $$$4$$$ millisecond the egg laying on top of the cell $$$(4,4)$$$ will be submerged by magma