紧急救援
测试数据来自 system/1513
背景
2008年是不平凡的一年
一件件的灾难
接二连三地席卷而来
特别是四川的地震灾难
我们失去了那么多的同胞
那么多的同胞失去了他们的家
那么多的同胞失去了他们的亲人
……
描述
在灾难发生之后,紧急救援部队立即赶往灾区,并在幸存者的帮助下一共找到了N名伤员
当然,由于伤员的受伤状况不同,所以治疗伤员的顺序影响着救活的伤员的数量
所以,你要找到一个最好的治疗顺序,使得救活伤员的总数最大
对于每一个伤员,用来描述其受伤状况的是两个正整数h,t.(单位:秒)
h表示他最晚的治疗完成时刻,t表示治疗他所需要的时间.(记当前时刻为0)
(如果正好在h时刻治疗完成,那么他也是能够救活的)
对于每一个伤员,h[i]在10小时之内,t[i]在1分钟到1小时之间.
格式
输入格式
第一行一个正整数N
接下来N行,每行两个整数:h和t,用一个空格隔开
输出格式
一个自然数,表示最大能够救活的人数
样例1
样例输入1
3
7 3
4 4
15 6
样例输出1
3
限制
各个测试点1s
提示
对于 50%的测试数据,N<=100
对于100%的测试数据,N<=50000