Problem1120--木匠PIPIⅡ

1120: 木匠PIPIⅡ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 691  Solved: 207
[Submit] [Status] [Web Board] [Creator:]

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

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

2
1
3

Source/Category