← 返回题目列表

AtCoder · abc038_d

D. 礼物

中文机器翻译题面 查看原题

問題文

高桥君决定准备一份礼物。礼物的内容已经决定了,现在剩下的就是准备装礼物的盒子了。 高桥君可以使用的箱子是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