TX202608 维修工的任务表

题目描述

维修工小林收到了 N 项维修任务，第 i 项任务需要连续工作 t_i 分钟，并且必须在第 d_i 分钟或之前完成。

所有任务都可以从第 0 分钟开始安排，没有其他开始时间限制。

小林同一时间只能处理一项任务。一项任务开始后，必须连续完成，不能暂停，也不能与其他任务交替进行。

小林可以自由决定：

• 接受哪些任务；
• 放弃哪些任务；
• 按什么顺序完成接受的任务。

只要任务完成时刻不超过它的截止时刻，就算按时完成。恰好在截止时刻完成也符合要求。

请你计算：小林最多可以按时完成多少项任务。

输入格式

第一行包含一个正整数 N，表示任务数量。

接下来 N 行，每行包含两个正整数 t_i 和 d_i，分别表示第 i 项任务的工作时间和截止时刻。

输出格式

输出一个整数，表示最多能够按时完成的任务数量。

样例输入

5
3 4
2 5
4 7
1 3
2 8

样例输出

3

样例说明

一种安排是依次完成第 4、2、5 项任务：

三项任务都能按时完成。

不存在能够按时完成四项任务的安排，因此答案为 3。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ t_i ≤ 10^9
• 1 ≤ d_i ≤ 10^9

子任务如下，各子任务独立计分：