Submission #2342115

---

Source Code Expand

N = int(input())
Q = [list(map(int, input().split())) for i in range(N)]
Q.sort(key=lambda x: x[1])
INF = 10**18
dp = [INF]*(N+1)
dp[0] = 0
for a, b in Q:
    for j in range(N-1, -1, -1):
        if dp[j] <= b-a and dp[j] + a <= dp[j+1]:
            dp[j+1] = dp[j] + a
ans = 0
for i in range(N+1):
    if dp[i] < INF:
        ans = i
print(ans)

Submission Info

Judge Result