3824木板 (farme)

3824   木板 (farme)

题目描述

有n个单位宽度的木板,每块木板的长度是Li.每块木板中间都有一个空槽,空槽必须在Pi处的钉子上,如图10.4-1所示。
现在,要选出尽可能多的木板并且将他们安排在一个直线上,使得没有两块木板相交(一个包含另外一个当然也是禁止的,不过边界相碰是允许的),空槽两端忽略不计,钉子也非常细,以安置在木板的边界,就是说木板的左端点的可能位置是Pi-Li至Pi.没有两颗钉子在同一个位置。


输入格式:

第1行1个正整数n,代表木板的数量(1<n< 100000).
接下来的每一行包含两个正整数Li和Pi(1<=Li, Pi<=10000000)代表第i块木板的长度,以及相关的钉子的位置。

输出格式:

输出一行一个整数,代表可以选择的最多的木板。
输入样例 复制
7
5 9
2 17
6 10
3 11
2 16
4 13
5 6
输出样例 复制
5

说明

0
0
通过提交
时空限制1000ms/64mb
题目来源
评测方式在线评测
题目类型queue
难        度