In a distant and mysterious land known as Quebec, there is a legend of a perfectly rectangular mountain of dimensions ~A \times B~ metres ~(1 \le A,B \le 20\,000)~ - legend also says that it's infinitely high. Due to a strange gas phenomenon, ~N~ ~(1 \le N \le 1\,000)~ 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 ~1~ 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 ~1~ 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.
Line ~1~: ~A~, ~B~, and ~N~ - respectively, the length of the West and North sides of the mountain (in metres) and the number of caves.
Lines ~2 \ldots N + 1~: ~Y1~, ~X1~, ~Y2~ and ~X2~ - the ~i~-th line gives the location of the ~(i-1)~-th cave, where ~Y1~ and ~Y2~ (~Y1 \le Y2~) are the distances of the sides of the cave from the North side of the mountain (in metres), and ~X1~ and ~X2~ (~X1 \le X2~) 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 ~N + 2~: ~Y~ and ~X~ -the location of the treasure (~Y~ metres from the North side of the mountain, and ~X~ metres from the West side). The treasure will lie within one of the caves.
A single number - the minimum amount of fuel Digger must use to reach the treasure (in millions of gallons).
11 12 3 1 2 1 4 3 5 3 5 5 5 5 6 5 6
A bird's-eye-view cross-section of the cave would look like this (
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 ~1~-st cave from the North
edge of the mountain - this requires ~1~ million gallons of fuel. He then
goes to the ~2~-nd cave, using another ~2~ million gallons.
Finally, he digs down to the ~3~-rd, using ~1~ million
gallons of fuel, and then walks to the East to claim the treasure. This
is a total of ~4~ million gallons ~(1+2+1)~. 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