← 返回题目列表

AtCoder · awc0019_e

E. 装载货物

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥正试图将纸板箱堆放在卡车床上以便移动。

高桥有 N 纸板箱,其中 i第一个盒子有重量 W_i 和负载能力 D_i。他选择了其中一些框(可能是 0,但每个框最多只能选择一次)并将选定的框以他喜欢的任何顺序从下到上堆叠在单列中。

但是,箱子有负载能力限制。如果放置在给定盒子顶部的所有盒子的总重量超过该盒子的负载能力(即严格大于负载能力),则该盒子将被压碎。如果总重量不超过负载能力,则箱子不会被压坏。即使有一个箱子被压坏,堆放也无效。

Takahashi 想要选择并堆叠箱子,以便堆叠有效。最大限度地增加堆叠中使用的箱子数量。

更准确地说:选择一个子集 S 来自 N 盒 (S 可能为空)。将盒子堆放在 S 在单列中从下到上按某种顺序排列。据说堆叠是 有效 如果,对于每个框 S,其上方所有箱子的总重量最多为该箱子的负载能力。一个子集 S 据说是 可行 如果存在至少一种盒子排序 S 使得堆叠有效。找到最大值 |S| 在所有可行子集中 S.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • 所有输入值均为整数。

输入

N
W_1 D_1
W_2 D_2
\vdots
W_N D_N
  • 第一行包含一个整数 N,纸箱数量。
  • 下一个 N 行给出每个框的信息。
  • 的 树的 (1 + i)第行包含重量 W_i 和负载能力 D_i 的 i第一个框,以空格分隔。

输出

在单行上打印最大值 |S| 在所有可行子集上 S,即可以选择的最大框数,使得堆叠有效。


示例输入 1

3
3 5
2 3
4 2

示例输出 1

2

示例输入 2

5
1 100
2 50
3 20
1 10
2 5

示例输出 2

5

示例输入 3

8
10 90
20 70
30 50
40 30
50 10
100 0
5 1000000000
1000000000 0

示例输出 3

5