War - Water Instead of Fire

A fire attack would be powerful, but the enemy has already anticipated it and camped where there are no trees. You decide to use water instead and flood the enemy's position.

There is an N * N map. The enemy is at (x, y), and water is poured from (1, 1). Each cell gives the depth to which the ground has been dug. If a cell contains water and one of its four adjacent cells has a lower current height, the water flows to that cell. The current height is determined by both the cell's depth and the water already filling it.

The water keeps flowing until it becomes stable, meaning no water in any cell can flow in another direction. Compute the minimum amount of water that must be poured so that the enemy cell is guaranteed to contain water of height at least k.

The first line contains the map size N and the required water height k at the enemy cell. N <= 400 and k <= 1,000,000.

The second line contains the enemy position x y.

Each of the next N lines contains the depths of one row of the map. No depth exceeds 1,000,000.

Print the minimum amount of water that must be poured.

If several stable states are possible after pouring water, you cannot know which one will occur. Therefore, the answer must be the minimum amount that guarantees the enemy cell is submerged by height k.

You may assume that water never leaves the N * N map.