题目描述

Elo 为了她远大的理想(购买一块农田)需要很多很多的钱,因此 Elo 去了一家电子厂上班。Elo 的上级每天会给 Elo 一个包含$n$项任务的清单,对于清单上的第$i$项任务,因为要等待前面的员工将该任务需要的部件送到她所属的车间,同时防止其它员工抢走这项任务,所以 Elo 只能在$s_i$时刻开始这项任务,并且需要$t_i$个时刻完成这项任务(即在$s_i+t_i$时刻完成任务)。Elo 在一个时刻只能专心致志做一项任务,并且只要开始做一项任务,她就必须将其完成。为了赚更多的钱,Elo 想要最大化每天完成的任务量,但是 Elo 每天做工已经身心俱疲,所以她希望你能帮她计算一天最多能够完成多少个任务。


输入格式

第一行,仅包含一个正整数$n(1\leqslant n \leqslant 10^5)$,表示任务的个数。
接下来有$n$行,对于第$i$行(即第$i$项任务),包含两个正整数,$s_i,t_i(1\leqslant s_i,t_i\leqslant 10^6)$,分别表示第$i$项任务开始的时刻以及 Elo 完成该项任务需要的时间。


输出格式

仅一行,包含一个正整数,表示 Elo 最多能够完成的任务数。


样例数据

输入

样例一
5
1 3
2 3
1 1
3 2
5 1

样例二
8
5 3
1 6
6 4
7 4
4 2
9 3
2 3
4 5

输出

样例一
3

样例二
3

备注

对于样例一,可以选择完成第$3,2,5$项或第$3,4,5$项任务,均为$3$项。


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解