Emptying the Baltic

Time limit3sMemory limit512 MB

Summary

Given a grid of altitudes and one drain cell, find the total water volume that can flow toward the drain, where water spreads to any of 8 neighbors at a lower level.

Level: Medium7 of 10
Topics: Graph, BFS, Heap, Greedy
Solved: No attempts yet

Problem

Gunnar dislikes forces of nature and always comes up with innovative plans to decrease their influence over him. His previous plan of a giant dome over Stockholm to protect the city from too much sunlight, rain and snow has not been realized yet, so he is now focusing on preempting the possible effects climate change might have on the Baltic Sea. His solution is simple: remove the Baltic from the equation.

First, Gunnar wants to build a floodbank connecting Denmark and Norway to separate the Baltic from the Atlantic Ocean. The floodbank also protects the Nordic countries from rising sea levels in the ocean. Next, Gunnar installs a device that can drain the Baltic from the seafloor. The device drains as much water as needed to the Earth's core, where it disappears forever (because that is how physics works, at least as far as Gunnar is concerned). However, depending on the placement of the device, the entire Baltic might not be completely drained. Some pockets of water may remain.

To simplify the problem, Gunnar approximates the map of the Baltic using a 2-dimensional grid of 1 meter squares. For each square on the grid he computes the average altitude. Squares with negative altitude are covered by water, squares with non-negative altitude are dry. Altitude is given in meters above the sea level, so the sea level has altitude of exactly 0. He disregards lakes and dry land below the sea level, as these would not change the estimate much anyway.

Water from a square on the grid can flow to any of its 8 neighbours, even if the two squares only share a corner. The map is surrounded by dry land, so water never flows outside of the map. Water respects gravity, so it can only flow closer to the Earth's core: either through the drainage device, or to a neighbouring square with a lower water level.

Gunnar is more of an idea person than a programmer, so he has asked for your help to evaluate how much water would be drained for a given placement of the device.

Input

The first line contains two integers $h$ and $w$ ( $1 \le h, w \le 500$ ), the height and the width of the map.

Then follow $h$ lines, each containing $w$ integers. The first line represents the northernmost row of Gunnar's map. Each integer is the altitude of one square on the map grid, given in meters, at least $-10^6$ and at most $10^6$ .

The last line contains two integers $i$ and $j$ ( $1 \le i \le h$ , $1 \le j \le w$ ), meaning that the draining device is placed in the cell corresponding to the $j$ -th column of the $i$ -th row. You may assume that position $(i, j)$ has negative altitude, so the draining device is never placed on land.

Output

Output one line with one integer, the total volume of sea water drained, in cubic meters.

Examples2

Example 1
Input
```
3 3
-5 2 -5
-1 -2 -1
5 4 -5
2 2
```
Expected output
```
10
```
Example 2
Input
```
2 3
-2 -3 -4
-3 -2 -3
2 1
```
Expected output
```
16
```