Problem D
Emptying the Baltic
First, Gunnar wants to build a floodbank connecting Denmark and Norway to separate the Baltic from the Atlantic Ocean. The floodbank will also help protect Nordic countries from rising sea levels in the ocean. Next, Gunnar installs a device that can drain the Baltic from the seafloor. The device will drain as much water as needed to the Earth’s core where it will disappear 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 is approximating the map of the Baltic using a $2$-dimensional grid with $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 via 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 \leq h, w \leq 500$, denoting the height and 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 represents the altitude of a square on the map grid. The altitude is given in meters and it is at least $-10^6$ and at most $10^6$.
The last line contains two integers $i$ and $j$, $1 \leq i \leq h, 1 \leq j \leq w$, indicating 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 (i.e., the draining device is not placed on land).
Output
Output one line with one integer – the total volume of sea water drained, in cubic meters.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 -5 2 -5 -1 -2 -1 5 4 -5 2 2 |
10 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 -2 -3 -4 -3 -2 -3 2 1 |
16 |
