TopCoder

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

67.3% (33/49)

Description

台北市有都市規劃了!所有建築物在東區地帶蓋成一排,而且沒有間距(沒有巷弄了!?)。它們形成一個極長的建築物群,從北向南延伸。
市長已經決定將建築物群的東方牆面貼滿海報(遮陽光?)。市長思考如何以最低數量的海報覆蓋整個建築物群的東面。海報都是長方形的。它們不能重疊,但可以互相接觸。每一張海報要完全貼在建築物的牆壁上。

Input Format

第一行的標準輸入包含一個整數 n (1<=n<=250,000),指建築物群的數目。
每一行包含兩個整數 di和 wi (1<=di ,wi<=1,000,000,000),由一個空格隔開,表示第i個建築物的長度與高度。

Output Format

輸出最少所需要的海報數。

Sample Input

5
1 2
1 3
2 2
2 5
1 4


Sample Output

4

Hints

Problem Source

原TIOJ1621 / Source: POI XV Postering
problem setter: 乃牛

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11