AtCoder Weekday Contest 0019 Beta E問題メモ

箱 $i$ までで暫定的に積み上げている箱の個数が同じなら、 $i+1$ 以降の箱のために、なるべく総重量は軽くしておいた方がいい。

上記の方法によって求められる $S$ は、 「$W_1～W_i$ の小さい方から $|Q|$ 個」の和となるので、 「$1～i$ の箱を使って $|Q|$ 個積み上げる中の総重量の下限」であることが保証される。 （できるかどうかはともかく、これ未満の総重量にする方法は無い）

よって、$D_{i+1} \lt S$ なら、どうやっても $i+1$ までで $|Q|+1$ 個を積み上げる方法は無い。
その結果、$S$ は「$1～i+1$ の箱を使って $|Q|$ 個積み上げる中の総重量の下限」に更新される。

（厳密に証明するなら、数学的帰納法で $|Q|=1$ の時で成立することも同時に示す）

あとは「実際に $Q$ 内の箱だけを使って積み上げることができる」、 つまり「入れ替え操作によって、潰れる箱が発生しない」ことが示せればよい。

入れ替え操作によって取り出される箱を $k$ とすると、$W_k \gt W_i$ である。
ここで、「$W_i+D_i$ が小さい順に操作している」ことが効いてきて、つまり $D_k \lt D_i$ である。

取り出した $k$ より、入れ替える $i$ の方が耐荷重が大きいことが保証されている。
$k$ と入れ替えることで箱 $i$ が潰れることはないし、 また、重量も小さくなるので $k$ の下にあった箱も、$i$ と入れ替えることで潰れることはない。

from heapq import heappush, heapreplace


def solve(n, boxes):
    boxes.sort(key=sum)
    hq = []
    total_weight = 0
    for w, d in boxes:
        if total_weight <= d:
            heappush(hq, -w)
            total_weight += w
        elif -hq[0] > w:
            total_weight += w + hq[0]
            heapreplace(hq, -w)
    return len(hq)


n = int(input())
boxes = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, boxes)
print(ans)