\(X_i=W_i+D_i\) とします。

まず \(N=2\) の場合を考えます。\(2\) つの段ボールを上から \(1,2\) 番という順に積み上げた場合の条件は \(W_1 \le D_2\) で、両辺に \(W_2\) を足すとこれは \(W_1+W_2 \le X_2\) となります。同様に、上から \(2,1\) 番という順に積み上げた場合の条件は \(W_1+W_2 \le X_1\) となります。

\(X_1 \le X_2\) が成り立つ場合 \(W_1+W_2 \le X_2\) という条件は \(W_1+W_2 \le X_1\) という条件よりも緩い（もしくは同じ）です。したがって、Exchange Argument より段ボールを \(X\) の昇順にソートしてナンバリングし直した際、最終的に積み上げた段ボールの番号は上から昇順になっているとして良いです。

実は、以下のような貪欲法で最大値を求めることができます：

• \(S=\lbrace \rbrace\) とする。
• \(i=1,2,\ldots,N\) に対して以下を行う。
  • \(S\) に \(i\) を追加する。
  • \(\displaystyle \sum_k W_k \le \max_k X_k\) が成り立たないなら \(S\) から \(W_j\) が最大となる \(j \in S\) を削除する。

証明：

\(i\) 回目のステップが終わった段階で \(S\) に含まれるインデックス \(j\) に対する \(W_j\) を昇順に並べた列を \(a_1^i \le a_2^i \le \ldots \le a_{m_i}^i\) とします（\(i=0\) では \(m_i=0\)）。

\(f_i(k)\) を「\(i\) 番目のダンボールまでで \(k\) 個潰れることなく積み上げた時の重さの合計の最小値、ただしそのような積み上げが不可能な場合は \(\infty\)」と定義します。このとき、以下の事実が成立します。

• \(k \le m_i\) のとき： \(\displaystyle f_i(k)=\sum_{j=1}^k a_j^i\)
• \(k > m_i\) のとき： \(f_i(k)=\infty\)

この事実を帰納法を用いて証明します。

• \(i=0\) のとき：明らかです。
• \(i\) での成立を仮定したとき：
  • 多重集合 \(\lbrace a_1^i,a_2^i,\ldots,a_{m_i}^i,W_{i+1}\rbrace\) の要素を昇順に並べた列を \(b_1 \le b_2 \le \ldots \le b_{m_i+1}\) とします。
  • (i) \(k\le m_i\) のとき：
    • \(f_{i+1}(k)\) の定義より明らかに \(\displaystyle f_{i+1}(k) \geq \sum_{j=1}^k b_i\) が成り立ちます。
    • そして、 \(i+1\) 個のダンボールの中から重さが > \(b_1,b_2,\ldots,b_k\) になるように \(k\) 個取って順番に積み重ねる方法は成立します。
      • もし \(i+1\) 番目のダンボールを使わないなら帰納法の仮定より成立します。
      • もし \(i+1\) 番目のダンボールを使うなら \(f_i(k-1)+W_{i+1} \le X_{i+1}\) より成立します。
    • 以上より、重さの総和が \(\displaystyle \sum_{j=1}^k b_i\) となる積み重ねかたが存在するので \(\displaystyle f_{i+1}(k) = \sum_{j=1}^k b_i\) が成立します。
  • (ii) \(k=m_i+1\) のとき：
    • \(m_i+1\) 個の並びを実現させるためにはダンボール \(i+1\) を必ず使う必要があります。重さの最小値は明らかに \(f_i(k)+W_{i+1}\) となるので、 \(f_{i+1}(m_i+1) < \infty\) は \(\displaystyle \sum_{j=1}^{m_i+1}b_j \le X_{i+1}\) と同値です。これは貪欲法のステップと一致します。
  • (i), (ii) より \(i\) での成立を仮定すると \(i+1\) での成立も従います。

以上より、\(f_N(m_N)\) の値を考えることで貪欲法が正答であることが分かります。

実装では優先度付きキューを用いることで簡潔に実装することができます。

実装例(Python3)

import heapq

n = int(input())
a = []
for i in range(n):
    w, d = map(int, input().split())
    a.append((w, w + d))
a.sort(key=lambda x: x[1])
q = []
sum_w = 0
for w, x in a:
    heapq.heappush(q, -w)
    sum_w += w
    if sum_w > x:
        ww = -heapq.heappop(q)
        sum_w -= ww
    assert sum_w <= x
print(len(q))