1775: 俄罗斯套娃信封

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:34 Solved:8

Description

      给你一个 n对整数的二维数组 nums ,其中 nums[i] = [wihi] ,表示第 i 个信封的宽度wi和高度hi。 当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 

      请计算 最多能有多少个 信封可以组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。注意:不允许旋转信封

      如有4个信封,其二维数组nums= [[54][64][67][23]] 。最多套娃信封的个数为 3个。从小到大为:  [23] => [54] => [67]。

   


Input

输入第一行为一个整数 n (1 ≤ n ≤100000)。

接下来的 n 行, 第 i+1 行包含两个整数 wi 和 hi。 wi表示第 i第 i 个信封的宽度,hi 表示第 i 个信封的高度 ( 1 ≤ wi,hi ≤100000)。

Output

输出一个整数,表示最多能有多少个信封,可以组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。注意:不允许旋转信封。

Sample Input Copy

4 
5 4
6 4
6 7
2 3 

Sample Output Copy

3

HINT

1 ≤ n ≤100000

1 ≤ wi,hi ≤100000