Picture
by Jeremy Halls on Flickr, cc by-sa
Gunnar dislikes forces of nature and always comes up with
innovative plans to decrease their influence over him. Even
though his previous plan of a giant dome over Stockholm to
protect from too much sunlight (as well as rain and snow) has
not yet been realized, he is now focusing on preempting the
possible effects climate change might have on the Baltic Sea,
by the elegant solution of simply removing 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 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 -dimensional grid with 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
. 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
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 and , , denoting the height and width of
the map.
Then follow lines,
each containing
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 and at most
.
The last line contains two integers and , , indicating that the
draining device is placed in the cell corresponding to the
’th column of the
’th row. You may assume
that position 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
|
