← 返回题目列表

AtCoder · chokudai_S002_l

L. 矩形 β

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

配点 : 600 点

問題文

N 矩形,并且矩形 i 的宽度和高度是 A_i, B_i 。

Snuke 可以选择其中一些矩形并按顺序堆叠它们。 1 我正在尝试制作两种图案。 这时, 放置的第j\ (2 \leq j) 个矩形必须满足以下条件。 完全包含在

  • j-1 放置的矩形内。 放置
  • j-1 的矩形的边不得相互接触。
  • 每边都是 它必须平行于 j-1 放置的矩形的一侧。

放置矩形时,请您可以交换宽度和高度。。另外,无论矩形的数量如何,都可以自由确定矩形的放置顺序。

Snuke 可以制作多少个重叠的矩形?

制約

输入满足以下条件。

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i,B_i \leq 10^9
  • 所有输入值均为整数

入力

输入将以以下形式从标准输入给出。

N
A_1 B_1
A_2 B_2
:
A_N B_N

出力

打印 Snuke 可以重叠的最大矩形数。 如果按照如图所示的顺序排列


入力例 1

4
3 4
1 5
5 5
3 1

出力例 1

3

長方形 3、長方形 1、長方形 4 , 3 您可以重叠两个矩形。 请注意,您可以交换矩形的宽度和高度。

d1833dc2257ec22da947ab7e7c018515.png

入力例 2

3
1000000000 1000000000
1000000000 1000000000
1000000000 1

出力例 2

1

请注意,边缘不得相互接触。