E - Loading Cargo Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は引っ越しのために、段ボール箱をトラックの荷台に積み上げようとしています。

高橋君は N 個の段ボール箱を持っており、i 番目の段ボール箱の重さは W_i、耐荷重は D_i です。高橋君はこれらの段ボール箱の中から何個か選び（0 個でもよいが、同じ段ボール箱を複数回選ぶことはできない）、選んだ段ボール箱を好きな順番で下から上へ一列に積み上げます。

ただし、段ボール箱には耐荷重の制限があります。ある段ボール箱の上に載っているすべての段ボール箱の重さの合計が、その段ボール箱の耐荷重を超えてしまう（すなわち、耐荷重より真に大きい）と、その段ボール箱は潰れてしまいます。重さの合計が耐荷重以下であれば潰れません。1 つでも潰れる段ボール箱があると、積み上げは成立しません。

高橋君は積み上げが成立するように段ボール箱を選んで積み上げたいと考えています。積み上げに使用する段ボール箱の個数を最大化してください。

より厳密に述べます。N 個の段ボール箱の中から部分集合 S を選びます（S は空集合でもよい）。S に含まれる段ボール箱を何らかの順番で下から上へ一列に積みます。S に含まれるすべての段ボール箱について、その段ボール箱より上にあるすべての段ボール箱の重さの合計がその段ボール箱の耐荷重以下であるとき、この積み上げは 成立する ものとします。ある S に対して、積み上げが成立するような積み上げ順が少なくとも 1 つ存在するとき、その 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
  • 1 行目には、段ボール箱の個数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目では、各段ボール箱の情報が与えられる。
  • 1 + i 行目では、i 番目の段ボール箱の重さ W_i と耐荷重 D_i がスペース区切りで与えられる。

出力

実現可能な S における |S| の最大値、すなわち積み上げが成立するように選べる段ボール箱の個数の最大値を 1 行で出力せよ。

入力例 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

Score : 433 pts

Problem Statement

Takahashi is trying to stack cardboard boxes onto a truck bed for moving.

Takahashi has N cardboard boxes, where the i-th box has weight W_i and load capacity D_i. He selects some of these boxes (possibly 0, but each box can be selected at most once) and stacks the selected boxes in a single column from bottom to top in any order he likes.

However, there is a load capacity constraint on the boxes. If the total weight of all boxes placed on top of a given box exceeds that box's load capacity (i.e., is strictly greater than the load capacity), that box will be crushed. If the total weight is at most the load capacity, the box will not be crushed. If even one box is crushed, the stacking is not valid.

Takahashi wants to select and stack boxes so that the stacking is valid. Maximize the number of boxes used in the stacking.

More precisely: select a subset S from the N boxes (S may be empty). Stack the boxes in S in some order in a single column from bottom to top. The stacking is said to be valid if, for every box in S, the total weight of all boxes above it is at most that box's load capacity. A subset S is said to be feasible if there exists at least one ordering of the boxes in S such that the stacking is valid. Find the maximum value of |S| among all feasible subsets S.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • All input values are integers.

Input

N
W_1 D_1
W_2 D_2
\vdots
W_N D_N
  • The first line contains an integer N, the number of cardboard boxes.
  • The next N lines give the information for each box.
  • The (1 + i)-th line contains the weight W_i and load capacity D_i of the i-th box, separated by a space.

Output

Print on a single line the maximum value of |S| over all feasible subsets S, that is, the maximum number of boxes that can be selected so that the stacking is valid.

Sample Input 1

3
3 5
2 3
4 2

Sample Output 1

2

Sample Input 2

5
1 100
2 50
3 20
1 10
2 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5