UOJ Logo 小司码 Online Judge

XSMOJ

第380题   木板

统计 下一题 上一题

题目描述

有n个单位宽度的木板,每块木板的长度是Li。每块木板中间都有一个空槽,空槽必须挂在Pi处的钉子上,如图所示。

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

输入格式

​第1行1个正整数n,代表木板的数量(1≤n≤100000)。

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

输出格式

输出一行一个整数,代表可以选择的最多的木板。

样例数据

input


7

5 9

2 17

6 10

3 11

2 16

4 13

5 6

output


5

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$64 \text{MB}$