Problem1048--木匠PIPIⅡ

1048: 木匠PIPIⅡ

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

木匠PIPI的作坊终于实现了自动化——引进了一台切木块的机器。有了机器后,PIPI现在可以切特别大的木块了~
木块可以用长度L和重量W来描述。机器的运作机制如下:
(1)机器切割第一块木头前需要1分钟的准备时间。
(2)在切割完一块长l、重w的木块后,若继续切割的木块长l'>=l且重w'>=w,则不需要准备时间,否则需要一分钟准备时间。
现在给你待切割的木块的长度和重量,问你最少需要多少准备时间~

Input

多组输入
第一行为一个整数n,表示木块数量。1<=n<=5000.
第二行为n对整数li,wi,分别为木块的长度和重量。1<=li,wi<=10000.

Output

输出最少准备时间

Sample Input Copy

5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

Sample Output Copy

2
1
3

Source/Category