Digger

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 16M

Author:

Problem type

In a distant and mysterious land known as Quebec, there is a legend of a perfectly rectangular mountain of dimensions $A \times B$ ~A \times B~ metres $(1 \le A,B \le 20\,000)$ ~(1 \le A,B \le 20\,000)~ - legend also says that it's infinitely high. Due to a strange gas phenomenon, $N$ ~N~ $(1 \le N \le 1\,000)$ ~(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$ ~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$ ~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.

Input Specification

Line $1$ ~1~: $A$ ~A~, $B$ ~B~, and $N$ ~N~ - respectively, the length of the West and North sides of the mountain (in metres) and the number of caves.
Lines $2 \dots N+1$ ~2 \dots N+1~: $Y_1$ ~Y_1~, $X_1$ ~X_1~, $Y_2$ ~Y_2~ and $X_2$ ~X_2~ - the $i$ ~i~-th line gives the location of the $(i-1)$ ~(i-1)~-th cave, where $Y_1$ ~Y_1~ and $Y_2$ ~Y_2~ $(Y_1 \le Y_2)$ ~(Y_1 \le Y_2)~ are the distances of the sides of the cave from the North side of the mountain (in metres), and $X_1$ ~X_1~ and $X_2$ ~X_2~ $(X_1 \le X_2)$ ~(X_1 \le X_2)~ 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$ ~N+2~: $Y$ ~Y~ and $X$ ~X~ - the location of the treasure ( $Y$ ~Y~ metres from the North side of the mountain, and $X$ ~X~ 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

Sample Output

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 $1$ ~1~-st cave from the North edge of the mountain - this requires $1$ ~1~ million gallons of fuel. He then goes to the $2$ ~2~-nd cave, using another $2$ ~2~ million gallons. Finally, he digs down to the $3$ ~3~-rd, using $1$ ~1~ million gallons of fuel, and then walks to the East to claim the treasure. This is a total of $4$ ~4~ million gallons $(1+2+1)$ ~(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

Comments

There are no comments at the moment.