这题有个trick,有可能单独一个矩形不满足切割条件,但是多个矩形的并满足切割条件
输入:
15
300 400
3
0 0 300 200
0 200 200 400
200 200 300 400
300 300
5
0 0 200 100
200 0 300 200
0 100 100 300
100 200 300 300
100 100 200 200
100 100
2
0 0 100 40
0 40 100 100
1000 1000
5
200 200 800 800
0 0 800 200
800 0 1000 800
0 200 200 1000
200 800 1000 1000
20 25
8
3 10 8 17
17 4 20 22
3 17 17 22
0 4 3 22
3 4 17 10
8 10 17 17
0 22 20 25
0 0 20 4
40000 40000
100
8000 20000 12000 24000
12000 4000 16000 8000
32000 12000 36000 16000
28000 0 32000 4000
12000 8000 16000 12000
4000 36000 8000 40000
28000 32000 32000 36000
8000 24000 12000 28000
16000 24000 20000 28000
0 28000 4000 32000
20000 20000 24000 24000
24000 28000 28000 32000
32000 20000 36000 24000
8000 12000 12000 16000
4000 28000 8000 32000
24000 8000 28000 12000
4000 0 8000 4000
32000 32000 36000 36000
20000 16000 24000 20000
0 0 4000 4000
16000 12000 20000 16000
28000 24000 32000 28000
32000 16000 36000 20000
16000 32000 20000 36000
14000 20000 16000 24000
12000 0 16000 4000
32000 0 36000 4000
32000 8000 36000 12000
12000 20000 14000 24000
20000 4000 24000 8000
36000 28000 40000 32000
8000 32000 12000 36000
4000 32000 8000 36000
20000 24000 24000 28000
32000 24000 36000 28000
32000 4000 36000 8000
24000 0 28000 4000
16000 16000 20000 20000
4000 24000 8000 28000
0 12000 4000 16000
4000 16000 8000 20000
24000 32000 28000 40000
16000 28000 20000 32000
24000 20000 28000 24000
28000 16000 32000 20000
20000 12000 24000 16000
36000 0 40000 4000
20000 32000 24000 36000
36000 36000 40000 40000
8000 16000 12000 20000
28000 8000 32000 12000
28000 4000 32000 8000
20000 36000 24000 40000
0 8000 4000 12000
8000 28000 12000 32000
8000 0 12000 4000
24000 12000 28000 16000
28000 12000 32000 16000
20000 8000 24000 12000
16000 4000 20000 8000
36000 12000 40000 16000
32000 28000 36000 32000
0 16000 4000 20000
4000 12000 8000 16000
0 20000 4000 24000
20000 0 24000 4000
12000 12000 16000 16000
16000 0 20000 4000
16000 8000 20000 12000
36000 32000 40000 36000
16000 36000 20000 40000
36000 8000 40000 12000
12000 32000 16000 36000
0 36000 4000 40000
0 4000 4000 8000
24000 24000 28000 28000
24000 16000 28000 20000
4000 8000 8000 12000
36000 20000 40000 24000
36000 16000 40000 20000
8000 36000 12000 40000
32000 36000 36000 40000
28000 36000 32000 40000
28000 20000 32000 24000
8000 8000 12000 12000
0 24000 4000 28000
8000 4000 12000 8000
12000 16000 16000 20000
12000 36000 16000 40000
16000 20000 20000 24000
4000 4000 8000 8000
36000 24000 40000 28000
4000 20000 8000 24000
36000 4000 40000 8000
12000 24000 16000 28000
24000 4000 28000 8000
12000 28000 16000 32000
20000 28000 24000 32000
28000 28000 32000 32000
0 32000 4000 36000
10 15
3
8 0 10 15
0 0 8 8
0 8 8 15
10 15
1
0 0 10 15
20 25
4
0 0 20 7
0 7 12 20
12 7 20 20
0 20 20 25
10 15
3
5 0 9 15
9 0 10 15
0 0 5 15
20 25
5
0 20 5 25
10 0 20 20
0 0 10 10
5 20 20 25
0 10 10 20
10 15
3
0 5 10 12
0 12 10 15
0 0 10 5
10000 10000
91
5000 8000 9000 9000
5500 3500 6000 4000
3000 6000 7000 7000
9800 9200 10000 9400
4500 3000 5000 3500
4500 4500 5000 5000
9800 9600 10000 9800
2000 1000 4000 2000
9600 9800 9800 10000
5500 5500 6000 6000
0 9000 6000 9333
5500 5000 6000 5500
0 3000 2000 5000
5000 3000 5500 3500
9400 9400 9600 9600
3500 5000 4000 5500
0 0 4000 1000
6000 9000 9000 9666
9000 3000 9333 9000
4000 4000 4500 4500
9600 9600 9800 9800
3000 7000 5000 9000
9333 6000 10000 9000
7000 4000 9000 6000
9600 9200 9800 9400
5000 5000 5500 5500
9800 9800 10000 10000
9200 9000 9400 9200
6000 2000 7000 6000
2000 3000 3000 7000
3500 4000 4000 4500
9600 9400 9800 9600
4500 5500 5000 6000
9600 9000 9800 9200
7000 2000 8000 4000
5000 5500 5500 6000
3000 3000 3500 3500
0 1000 2000 3000
3000 5500 3500 6000
0 9333 3000 10000
3500 3000 4000 3500
9200 9800 9400 10000
9200 9600 9400 9800
3000 9666 9000 10000
9200 9200 9400 9400
5000 3500 5500 4000
9000 9400 9200 9600
9800 9000 10000 9200
3500 3500 4000 4000
4500 3500 5000 4000
4000 4500 4500 5000
9200 9400 9400 9600
3000 9333 6000 9666
6000 0 8000 2000
5500 4000 6000 4500
1000 5000 2000 7000
3000 5000 3500 5500
8000 0 9000 4000
9000 9600 9200 9800
4000 3500 4500 4000
9400 9200 9600 9400
4500 4000 5000 4500
4000 5000 4500 5500
2000 2000 6000 3000
9400 9600 9600 9800
9666 0 10000 6000
9333 3000 9666 6000
5500 3000 6000 3500
9000 9000 9200 9200
3000 4000 3500 4500
9800 9400 10000 9600
9000 0 9666 3000
5500 4500 6000 5000
5000 4500 5500 5000
3000 3500 3500 4000
5000 4000 5500 4500
5000 7000 7000 8000
4000 3000 4500 3500
9400 9800 9600 10000
3000 4500 3500 5000
9400 9000 9600 9200
4000 5500 4500 6000
4000 0 6000 2000
7000 6000 9000 8000
0 5000 1000 9000
1000 7000 3000 9000
4500 5000 5000 5500
9000 9200 9200 9400
3500 4500 4000 5000
9000 9800 9200 10000
3500 5500 4000 6000
1100 1200
98
500 400 600 500
100 200 200 300
100 600 200 700
200 700 300 800
400 700 500 800
1000 500 1100 600
600 400 700 500
1000 100 1100 200
100 700 200 800
800 800 900 900
300 400 400 500
300 0 400 100
500 600 600 700
700 400 800 500
100 1000 200 1100
300 1000 400 1100
700 0 800 100
1000 1000 1100 1100
300 300 400 400
500 0 600 100
500 1000 600 1100
800 1000 900 1100
100 300 200 400
800 200 900 300
1000 0 1100 100
1000 800 1100 900
200 200 300 300
800 600 900 700
1000 200 1100 300
500 900 600 1000
800 400 900 500
700 500 800 600
600 800 700 900
400 300 500 400
600 500 700 600
300 900 400 1000
1000 300 1100 400
200 1000 300 1100
1000 700 1100 800
900 0 1000 100
600 1000 700 1100
600 600 700 700
200 0 300 100
200 300 300 400
100 900 200 1000
1000 900 1100 1000
300 200 400 300
800 500 900 600
600 300 700 400
600 200 700 300
200 800 300 900
100 400 200 500
1000 400 1100 500
800 900 900 1000
500 500 600 600
800 300 900 400
100 1100 1000 1200
500 700 600 800
400 800 500 900
200 600 300 700
200 900 300 1000
400 1000 500 1100
700 1000 800 1100
500 800 600 900
0 0 100 100
700 700 800 800
400 400 500 500
100 500 200 600
1000 600 1100 700
400 500 500 600
1000 1100 1100 1200
700 900 800 1000
900 100 1000 1100
0 100 900 200
0 200 100 1200
300 800 400 900
200 400 300 500
100 0 200 100
700 800 800 900
800 0 900 100
100 800 200 900
300 700 400 800
200 500 300 600
500 300 600 400
700 600 800 700
500 200 600 300
700 200 800 300
600 0 700 100
800 700 900 800
300 500 400 600
400 200 500 300
600 700 700 800
600 900 700 1000
400 900 500 1000
300 600 400 700
400 600 500 700
400 0 500 100
700 300 800 400
10 15
2
0 0 10 7
0 7 10 15


输出
60000
90000
6000
1000000
84
32000000
64
150
156
75
200
70
81000000
1100000
80