3379 - 排雷
题目描述
小 A 正在玩一个新款的排雷游戏。
这款游戏在界面上共有 N 颗地雷。拆除第 i 颗地雷需要 C_i 秒的时间，如果从游戏开始计时到第 T_i 秒结束（即：秒表已经到了第 T_i+1 秒），第 i 颗地雷还未拆除，该地雷会立刻爆炸。
紧张的游戏开始了，请你帮小 A 计算出，如果他合理安排拆除地雷的顺序，最多能拆除多少个地雷？
输入
第 1 行输入一个整数 N。
接下来 N 行，每行输入 2 个整数 C_i 和 T_i ，含义如题所述。
本题假设如果小 A 在第 X 秒完成某地雷的拆除，会立刻在第 X+1 秒拆除下一个地雷，不会浪费任何合适时间。
输出
输出小 A 最多能拆除地雷的数量。
样例
输入
5 90 210 2100 3500 1000 1250 180 1200 800 3800
输出
4
输入
10 9 17 24 32 30 38 10 18 12 20 15 23 19 27 37 45 45 53 50 60
输出
2
输入
12 40 100 30 120 80 150 25 200 60 220 120 300 50 350 90 400 200 500 70 550 150 600 110 800
输出
9
说明
样例 1 解释
共有 5 颗地雷，按照以下顺序，可以拆除 4 颗。按照输入的顺序为 5 颗地雷编号为 1 \sim 5。
耗时 90 秒排除第 1 颗地雷。
接下来耗时 180 秒排除第 4 颗地雷，此时共耗费时间 270 秒。
接下来耗时 2100 秒排除第 2 颗地雷，此时共耗费时间 2370 秒。
接下来耗时 800 秒排除第 5 颗地雷，此时共耗费时间 3170 秒。
数据范围
对于 30\% 的数据，1 \le N \le 800。
对于 100\% 的数据，1 \le N \le 1.5 \times 10^5，1 \le C_i \lt T_i \lt 2^{31}。
标签
