题目描述
N 名迷途的旅者需要小 X 的指引。
初始时,每一名旅者 i 位于坐标 (Ai,Bi) 处。旅者们只能够向右或向上移动,也就是说,他们只能够增加自己的某一维坐标,而不能减小它们。
这片大地上同样存在着 N 个出口,每一个出口 i 位于坐标 (Ci,Di) 处。一个出口一旦被某个旅者通过,该旅者和该出口就会一并消失。
请帮助小 X 计算他至多能够指引多少旅者离开这片大地。
【输入格式】
从文件 guide.in 中读取数据。
第一行一个整数 Num,表示测试点编号,以便选手方便地获得部分分。你可能不需要用到这则信息。样例中 Num 的含义为数据范围与某个测试点相同。
接下来一行一个整数 N,含义见题目描述。
接下来 N 行,每行两个整数 Ai,Bi,表示每一名旅者的坐标。
接下来 N 行,每行两个整数 Ci,Di,表示每一个出口的坐标。
【输出格式】
将结果输出到文件 guide.out 中。
一行一个整数,表示答案。
【样例 1 】
6
3
2 0
3 1
1 3
4 2
0 4
5 5
2
【样例 1 解释】
让位于 (2,0) 的旅者走到 (4,2) 处,让位于 (3,1) 的旅者走到 (5,5) 处。
【样例 2~5】
见下发文件 。
【数据范围及子任务】
对于所有测试数据,保证 1⩽N⩽105,0⩽Ai,Bi,Ci,Di<2N。
保证 A1,A2,…,AN,C1,C2,…,CN 两两不同。
保证 B1,B2,…,BN,D1,D2,…,DN 两两不同。
特殊性质 1:保证 Ai=Bi。
特殊性质 2:保证 Ci=Di。
| 测试点编号 |
N |
特殊性质 1 |
特殊性质 2 |
| 1 |
=1 |
YES |
YES |
| 2 |
=2 |
| 3 |
⩽5 |
| 4 |
NO |
| 5 |
⩽10 |
| 6 |
NO |
| 7 |
⩽20 |
YES |
YES |
| 8 |
NO |
| 9 |
NO |
| 10 |
| 11 |
⩽100 |
YES |
YES |
| 12 |
| 13 |
NO |
| 14 |
| 15 |
NO |
| 16 |
| 17 |
⩽103 |
| 18 |
| 19 |
| 20 |
⩽105 |