In a distant and mysterious land known as Quebec, there is a legend of a perfectly rectangular mountain of dimensions metres - legend also says that it's infinitely high. Due to a strange gas phenomenon, perfectly rectangular caves (with their sides parallel to those of the mountain) have formed, all at ground level. When viewed as a top-down cross-section, each metre by metre square at ground level can be said to either contain solid rock, be hollow, or contain the treasure. There is only such treasure.
The famous adventurer known only as "Digger" has learnt of this mountain and its treasure, and of course he wants to get to it. Fortunately, he isn't called "Digger" for nothing - he possesses a special machine which can remove all the rock from a metre by metre square (he refuses to tell us where this rock ends up), with the incredible fuel consumption of million gallons per such an operation. Digger can walk freely around any open space, both natural and artificial, but since he's restricted to the ground, the height of the caves doesn't matter. Though Digger is pretty rich, he still wishes to minimize the amount of fuel he uses to reach the treasure.
Digger can start anywhere on the outside of the mountain. Determine the minimum amount of fuel he must use to reach the treasure.
Input Specification
Line : , , and - respectively, the length of the West and North sides of the mountain (in metres) and the number of caves.
Lines : , , and - the -th line gives the location of the -th cave, where and are the distances of the sides of the cave from the North side of the mountain (in metres), and and are the distances from the West side. No two caves will overlap or touch at a corner or side, and all caves will be completely inside the mountain.
Line : and - the location of the treasure ( metres from the North side of the mountain, and metres from the West side). The treasure will lie within one of the caves.
Output Specification
A single number - the minimum amount of fuel Digger must use to reach the treasure (in millions of gallons).
Sample Input
11 12 3
1 2 1 4
3 5 3 5
5 5 5 6
5 6
Sample Output
4
Explanation for Sample Output
A bird's-eye-view cross-section of the cave would look like this (x
:
solid rock, .
: cave, T
: treasure):
0 2 4 etc
0 xxxxxxxxxxxx
xx...xxxxxxx
2 xxxxxxxxxxxx
xxxxx.xxxxxx
4 xxxxxxxxxxxx
xxxxx.Txxxxx
e xxxxxxxxxxxx
t xxxxxxxxxxxx
c xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
Digger starts by tunnelling to the -st cave from the North
edge of the mountain - this requires million gallons of fuel. He then
goes to the -nd cave, using another million gallons.
Finally, he digs down to the -rd, using million
gallons of fuel, and then walks to the East to claim the treasure. This
is a total of million gallons . One possible set of digging
sites is shown below (D
: dig here):
xxDxxxxxxxxx
xx...xxxxxxx
xxxxDDxxxxxx
xxxxx.xxxxxx
xxxxxDxxxxxx
xxxxx.Txxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
Comments