問題文
高桥君决定准备一份礼物。礼物的内容已经决定了,现在剩下的就是准备装礼物的盒子了。 高桥君可以使用的箱子是N可用, 编号至i盒子是垂直的。h_i厘米×宽度w_i尺寸为厘米。
高桥君觉得礼物装在更多的盒子里会更有趣,所以他决定尽可能多地套上盒子,把礼物放在最里面的盒子里。 某个盒子只能放入垂直和水平都较大的盒子中。还有,某个盒子1您最多只能装入另一个盒子。
请告诉我礼物嵌套盒的最大数量。 如果所有满足
制約
- 1≦N≦10^5
- 1≦h_i≦10^5
- 1≦w_i≦10^5
部分点
- N ≦ 1,000 的测试用例都被正确回答,将给出部分分数。30点。 如果您正确回答
入力
输入将以以下格式从标准输入提供。
N w_1 h_1 w_2 h_2 : w_N h_N
出力
包装礼物的盒子的最大数量。 在 1 行输出。
入力例1
3 3 3 1 1 2 2
出力例1
3
从外包装盒开始, 您可以将礼物包装在1, 3, 2框中。
入力例2
2 4 5 4 3
出力例2
1
盒子 请注意,无法旋转90度。另外,一个盒子不能放在一个长度或宽度相等的盒子里。
入力例3
4 2 5 3 3 4 5 6 6
出力例3
3
入力例4
5 8 8 5 3 2 2 4 2 2 1
出力例4
4