1949 - [Ceoi2006]Walk

考虑X-Y平面上满足X≥0的整数结点给定若干个矩形及一个目标点，紧靠每个矩形外部的一周范围内没有其它矩形的点，所有矩形中的所有点满足X≥0 求一条以(0,0)点为起点，以目标点为终点、不与任何矩形相交的最短路径

输入

第一行输入为两个整数X与Y(1≤X≤106,-106≤Y≤106)表示目标点坐标第二行为一个整数N(0≤N≤105)，表示矩形的数目接下来的N行每行包括4个整数： X1,Y1,X2,Y2(0≤X1,X2≤106,0≤Y1,Y2≤106) 即N个矩形的某对对角顶点。

输出

第一行包括一个整数L，表示最短路径长度

样例

输入

42 33
66
35 37 37 37
13 -41 13 6
40 -2 42 -1
27 -2 28 -2
15 -4 16 2
29 16 29 16
38 -34 38 -11
22 -5 22 -5
34 27 34 35
28 12 29 12
10 11 11 13
11 25 11 25
24 4 25 40
27 9 27 10
27 -4 27 -4
29 7 29 10
3 -13 5 -13
16 17 16 17
18 6 18 48
4 7 4 14
5 2 5 5
40 22 44 32
21 13 21 13
34 3 34 25
41 11 42 20
15 -15 16 -9
24 -46 25 -6
5 -4 5 -3
10 17 11 17
28 14 29 14
3 -15 4 -15
10 15 10 15
16 8 16 9
2 2 2 2
1 -4 3 -3
10 21 10 21
22 8 22 8
20 -3 21 2
10 19 11 19
7 -47 8 3
28 -11 28 -6
20 4 20 9
11 23 11 23
15 -17 16 -17
27 0 27 3
43 5 43 8
15 -7 16 -6
16 -19 16 -19
11 -10 11 -10
21 11 22 11
4 0 4 0
15 5 16 6
3 -11 5 -7
11 -8 11 -1
28 -13 28 -13
21 15 22 15
40 -30 43 -5
41 34 43 35
15 14 16 15
21 -16 22 -13
1 -1 2 -1
10 1 11 9
22 17 22 17
31 -50 32 -1
22 -8 22 -7
16 -21 16 -21

输出

时间限制	1 秒
内存限制	128 MB

统计

上一题下一题