Digger

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

Input

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..N+1: Y1, X1, Y2 and X2 — the i-th line gives the location of the (i-1)-th cave, where Y1 and Y2 (Y1Y2) are the distances of the sides of the cave from the North side of the mountain (in metres), and X1 and X2 (X1X2) 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.
Lines 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.

Output

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

Explanation

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

Sample Output

4

Explanation

Digger starts by tunnelling to the 1st cave from the North edge of the mountain - this requires 1 million gallons of fuel. He then goes to the 2nd cave, using another 2 million gallons. Finally, he digs down to the 3rd cave, 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

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Oct 05, 2008
Author: SourSpinach

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Notice how big the coordinates of the caves can be - up to 20000. This means you can't store the whole mountain in an array similar to the diagram shown in the problem description (however, if you do, you'll still get partial marks).

Anyway, this means that the solution doesn't really have anything to do with how big the caves can get. As such, try treating each cave as a single "position", and figure out how much fuel it takes to get from one cave to another (since they're all rectangular, this isn't hard). That's a start.