当前没有测试数据。

题目描述

你有一个单线程处理器和 N 个待处理任务。每个任务 i 有两个参数：

• tᵢ：处理该任务所需的连续时间（单位时间）。
• dᵢ：该任务的截止时间（从时刻 0 开始计时）。

规则：

• 任务一旦开始就不能中断（非抢占式）。
• 一个任务处理完后，可立即开始下一个任务。
• 如果任务 i 的完成时间（该任务结束的时刻）≤ dᵢ，则认为该任务按时完成。

你可以自由决定任务的执行顺序。目标是最大化按时完成的任务数量。

请输出最多可以按时完成的任务数。

输入格式

N
t₁ d₁
t₂ d₂
...
tₙ dₙ

• 第一行：整数 N（1 ≤ N ≤ 10⁵）
• 接下来 N 行：每行两个整数 tᵢ 和 dᵢ（1 ≤ tᵢ, dᵢ ≤ 10⁹）

输出格式

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

样例

样例1：

输入：
3
3 5
2 4
1 3

输出：
2

解释：
按 (t,d) 列出：(3,5), (2,4), (1,3)

策略：先做 (1,3)，时刻 1 完成 ≤ 3 ✓
      再做 (2,4)，时刻 1+2=3 完成 ≤ 4 ✓
      最后做 (3,5)，时刻 3+3=6 完成 > 5 ✗
共完成 2 个。

其他顺序均无法完成超过 2 个：
  先做 (3,5)：时刻 3 ≤ 5 ✓，但剩余任务都会超时。
  先做 (2,4)：时刻 2 ≤ 4 ✓，再做 (1,3)：时刻 3 ≤ 3 ✓，再做 (3,5)：时刻 6 > 5 ✗（也是 2 个）。

样例2：

输入：
4
1 2
1 3
2 4
3 7

输出：
4

解释：
按截止时间排序：(1,2), (1,3), (2,4), (3,7)
全部按时完成：
  (1,2): 时刻 1 ≤ 2 ✓, 总时间=1
  (1,3): 时刻 2 ≤ 3 ✓, 总时间=2
  (2,4): 时刻 4 ≤ 4 ✓, 总时间=4
  (3,7): 时刻 7 ≤ 7 ✓, 总时间=7
全部完成，答案为 4。

样例3：

输入：
5
4 5
3 6
2 3
5 10
1 2

输出：
3

解释：
按截止时间排序：(1,2), (2,3), (4,5), (3,6), (5,10)
  (1,2): 总时间=1 ≤ 2 ✓, 堆={1}
  (2,3): 总时间=3 ≤ 3 ✓, 堆={2,1}（最大堆：2,1）
  (4,5): 总时间=7 > 5 ✗, 弹出最大耗时 4, 总时间=3, 堆={2,1}
  (3,6): 总时间=6 ≤ 6 ✓, 堆={3,2,1}
  (5,10):总时间=11 > 10 ✗, 弹出最大耗时 5, 总时间=6, 堆={3,2,1}
最终堆大小 = 3，即完成 3 个任务。

数据范围与约束