Problem:


Score : 700 points

Problem Statement

In the final of CODE FESTIVAL in some year, there are N participants.
The height and power of Participant i is H_i and P_i, respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton.
Initially, the stack is empty.
When it is Participant i's turn, if there are H_i or less zabuton already stacked, he/she will add exactly P_i zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack.
How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

1 \leq N \leq 5000

0 \leq H_i \leq 10^9

1 \leq P_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
H_1 P_1
H_2 P_2
:
H_N P_N

Output

Print the maximum number of participants who can add zabuton to the stack.

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants 1 and 3 will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is 2.

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order 2, 3, 1, all of them will be able to add zabuton.

Sample Input 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

Sample Output 3

5



Sample input:
3
0 2
1 3
3 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
N = int(input())
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
dp = [[5001 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(N+1):
        if dp[i-1][j-1] <= HP[i-1][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(N,-1,-1):
    if dp[-1][i] != 5001:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
H = 0
count = 0
for h,p in HP:
    if h >= H:
        H += p
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
participants = []
for _ in range(n):
    h, p = map(int, input().split())
    participants.append([h, p])
participants = sorted(participants, key=lambda x: x[1])

cnt = 1
current_height = participants[0][1]
for participant in participants:
    if current_height <= participant[0]:
        current_height += participant[1]
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    human = [tuple(map(int, input().split())) for _ in range(N)]

    human.sort(key = lambda x: (x[1]+x[0]))
    inf = 1000000001
    #iからj人乗せた中で最小座布団
    dp = [[inf]*(N+1) for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] <= human[i][0]:
                dp[i+1][j+1] = min(dp[i][j+1], dp[i][j] + human[i][1])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    ans = 0
    for i in range(N+1):
        if dp[N][i] != inf:
            ans = i

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    human = [tuple(map(int, input().split())) for _ in range(N)]

    human.sort(key = lambda x: (x[1]+x[0]))
    inf = 1000000001
    #iからj人乗せた中で最小座布団
    dp = [[inf]*(N+1) for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] <= human[i][0]:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + human[i][1])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    ans = 0
    for i in range(N+1):
        if dp[N][i] != inf:
            ans = i

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    human = [tuple(map(int, input().split())) for _ in range(N)]

    human.sort(key = lambda x: (x[1], x[0]))
    inf = 100000000000001
    #iからj人乗せた中で最小座布団
    dp = [[inf for i in range(N+1)] for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] <= human[i][0]:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + human[i][1])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    ans = 0
    for i in range(N+1):
        if dp[N][i] != inf:
            ans = i

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
human = [list(map(int, input().split())) for i in range(N)]

human.sort(key = lambda x: (x[1], x[0]))
inf = 10000000001
#iからj人乗せた中で最小座布団
dp = [[inf for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(N):
        if dp[i][j] <= human[i][0]:
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + human[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(N+1):
    if dp[N][i] != inf:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
human = [list(map(int, input().split())) for i in range(N)]

human.sort(key = lambda x: (x[1], x[0]))
inf = 100000000001
#iからj人乗せた中で最小座布団
dp = [[inf for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(N):
        if dp[i][j] <= human[i][0]:
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + human[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(N+1):
    if dp[N][i] != inf:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
cs = sorted((tuple(map(int, input().split())) for _ in range(n)), key=itemgetter(1, 0))
dp = [0]
for m, (h, p) in enumerate(cs):
    if dp[-1] <= h:
        dp.append(dp[-1] + p)
        bak = 3
    else:
        bak = 2
    for i in range(len(dp) - bak, -1, -1):
        if dp[i] <= h:
            dp[i + 1] = min(dp[i + 1], dp[i] + p)

print(len(dp) - 1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
cs = sorted((tuple(map(int, input().split())) for _ in range(n)), key=itemgetter(1))
dp = [0]
for m, (h, p) in enumerate(cs):
    if dp[-1] <= h:
        dp.append(dp[-1] + p)
        bak = 3
    else:
        bak = 2
    for i in range(len(dp) - bak, -1, -1):
        if dp[i] <= h:
            dp[i + 1] = min(dp[i + 1], dp[i] + p)

print(len(dp) - 1)

Submission status: Wrong Answer

Solution code:
inf = 1e18

N = int(raw_input())
HP = sorted(sorted([map(int, raw_input().split()) for i in xrange(N)]), key = lambda x:x[1])
dp =[inf] * 5005

for i in xrange(N):
    H, P = HP[i]
    for j in xrange(N + 1, -1, -1):
        if dp[j] < inf and dp[j] <= H:
            dp[j + 1] = min(dp[j + 1], dp[j] + P)
    dp[1] = min(dp[1], P)

ans = max(i for i in xrange(N + 1) if dp[i] < inf)

print ans

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = []
for _ in range(n):
    lis.append(list(map(int,input().split())))
hs = sorted(lis)
ps = sorted(hs,key=lambda x: x[1])
zab,c = 0,0
for i in range(n):
    h,p = ps[i]
    if zab <= h:
        zab += p
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
# D問題
import heapq
N = int(input())
heap = []

for i in range(N):
	H,P = map(int,input().split(" "))
	heap.append((P,H))

heapq.heapify(heap)

height = 0
count = 0

while heap != []:
	man = heapq.heappop(heap)
	if man[1] >= height:
		height += man[0]
		count += 1 


print(count)

Submission status: Wrong Answer

Solution code:
import collections
import itertools
N = int(input())
M = [list(map(int, input().split())) for i in range(N)]
M_sorted = sorted(M, key=lambda x:(x[0], x[1]))

ans, count = 0, 0
for i in M_sorted:
    if ans <= i[0]:
        ans += i[1]
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
import collections
import itertools
N = int(input())
M = [list(map(int, input().split())) for i in range(N)]
M_sorted = sorted(M, key=lambda x:(x[1], x[0]))

ans, count = 0, 0
for i in M_sorted:
    if ans <= i[0]:
        ans += i[1]
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
PHs = []
for i in range(N):
    H, P = map(int, input().split())
    PHs.append((P, H))

PHs.sort()

memo = {0: 0}
for i, (P, H) in enumerate(PHs):
    for num in list(memo.keys()):
        if H >= memo[num]:
            if num + 1 in memo:
                memo[num + 1] = min(memo[num + 1], memo[num] + P)
            else:
                memo[num + 1] = memo[num] + P

print(max(memo.keys()))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n = int(input())
lis = []
for i in range(n):
    data = list(map(int, input().split()))
    lis.append(data)
sortlis = sorted(lis, key=itemgetter(1,0))

curh = sortlis[0][1]
ans = 1
for i in sortlis[1:]:
    if curh<=i[0]:
        curh+=i[1]
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ds = []
for i in range(N):
  ds.append(list(map(int, input().split())))

ds.sort(key=lambda x:(x[0]+x[1], x[1]))

l = 0
ans = 0
for d in ds:
  h, p = d
  if l <= h:
    ans += 1
    l += p

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ds = []
for i in range(N):
  ds.append(list(map(int, input().split())))

ds.sort(key=lambda x:x[0]+x[1])

l = 0
ans = 0
for d in ds:
  h, p = d
  if l <= h:
    ans += 1
    l += p

print(ans)

Submission status: Wrong Answer

Solution code:
inf = 1e18

N = int(raw_input())
HP = sorted(sorted([map(int, raw_input().split()) for i in xrange(N)]), key = lambda x:x[1])
print HP
dp =[inf] * 5005

for i in xrange(N):
    H, P = HP[i]
    for j in xrange(N + 1, -1, -1):
        if dp[j] < inf and dp[j] <= H:
            dp[j + 1] = min(dp[j + 1], dp[j] + P)
    dp[1] = min(dp[1], P)

ans = max(i for i in xrange(N + 1) if dp[i] < inf)

print ans

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
dp = [[float('inf') for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(N+1):
        if dp[i-1][j-1] <= HP[i-1][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(N,-1,-1):
    if dp[-1][i] != float('inf'):
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = []
for i in range(N):
    h, p = map(int, input().split())
    d.append((h, p))

d = sorted(d, key=lambda x: x[0] + x[1])
INF = float('inf')
dp = [[INF] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(N + 1):
        dp[i][j] = dp[i - 1][j]
        if j == 0:
            continue
        if dp[i - 1][j - 1] > d[i - 1][0]:
            continue
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + d[i - 1][1])

for i in range(N, -1, -1):
    if dp[N][i] < INF:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()


dp=[[10**23]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    for j in range(1,N+1):
        #print(A[i-1])
        if dp[i-1][j-1]>A[i-1][1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+A[i-1][2])
for j in range(N,-1,-1):
    if dp[N][j]<10**23:
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([LI() for _ in range(n)], key = lambda x: sum(x))
    d = {}
    d[0] = 0
    for h,p in a:
        s = copy.copy(d)
        for k,v in d.items():
            if h < k:
                continue
            nk = k + p
            if nk not in s or s[nk] < v+1:
                s[nk] = v+1
        d = s

    return max(d.values())



print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
cs = sorted((tuple(map(int, input().split())) for _ in range(n)), key=sum)
dp = [0]
for m, (h, p) in enumerate(cs):
    if dp[-1] <= h:
        dp.append(dp[-1] + p)
        bak = 3
    else:
        bak = 2
    for i in range(len(dp) - bak, -1, -1):
        if dp[i] <= h:
            dp[i + 1] = min(dp[i + 1], dp[i] + p)

print(len(dp) - 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for i, (H, P) in enumerate(HPs, 1):
    if dp[-1] != INF:
        dp += [INF]

    for j in range(1, len(dp))[::-1]:
        hgt = dp[j - 1]
        if hgt <= H:
            dp[j] = min(dp[j], hgt + P)

dp += [INF]
print(dp.index(INF) - 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for H, P in HPs:
    if dp[-1] != INF:
        dp += [INF]
    dp = list(map(min, zip([0] + [hgt + P if hgt <= H else INF for hgt in dp], dp)))

dp += [INF]
print(dp.index(INF) - 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

dp = {0: 0}
for H, P in HPs:
    for num, minH in list(dp.items()):
        if H >= minH:
            if num + 1 in dp:
                dp[num + 1] = min(dp[num + 1], minH + P)
            else:
                dp[num + 1] = minH + P

print(max(dp.keys()))

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline().strip())

X = []

for i in range(N):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    X += [(vs[0], vs[1])]

X = sorted(X, key=lambda x:(x[1],x[0]))

def choice(h, X):
    rm = -1
    ri = -1
    for i, x in enumerate(X):
        hn = h + x[1]
        rr = sum(1 for j, y in enumerate(X) if y[0] >= hn and i != j)
        #print(i, hn, h, x[0], rr)
        if rr > rm:
            ri = i
            rm = rr
    if rm == -1:
        return None
    return ri

n = 0
h = 0
while 1:
    i = choice(h, X)
    if i == None:
        break
    #print(X[i])
    h += X[i][1]
    X = X[:i] + X[i+1:]
    n += 1
    if len(X) == 0: break
    if max(x[0] for x in X) < h: break

#print(h, X)
print(n)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n = int(input())
    hp = [[int(i) for i in input().split()] for _ in range(n)]
    hp.sort(key=lambda x:(x[1], x[0]))
    ans = {0:[0, 0]}
    for h, p in hp:
        ta = dict(ans)
        for a in ta.keys():
            if ta[a][0] <= h:
                tmax = ta[a][1] + 1
                t = a + p
                if t in ans:
                    tmax = max(tmax, ans[t][1])
                ans[t] = [ta[a][0] + p, tmax] 
    print(max([i[1] for i in ans.values()]))

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools
N = int(input())
M = [list(map(int, input().split())) for i in range(N)]

P = list(itertools.permutations(M))

count = 0
for pattern in P:

    ans_tmp, count_tmp = 0, 0
    for i in pattern:
        if ans_tmp <= i[0]:
            ans_tmp += i[1]
            count_tmp += 1
    count = max(count, count_tmp)

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
PHs = []
for i in range(N):
    H, P = map(int, input().split())
    PHs.append((P, H))

PHs.sort()

memo = {0: 0}
for i, (P, H) in enumerate(PHs):
    for hgt in list(memo.keys()):
        if H >= hgt:
            if hgt + P in memo:
                memo[hgt + P] = max(memo[hgt + P], memo[hgt] + 1)
            else:
                memo[hgt + P] = memo[hgt] + 1

print(max(memo.values()))

Submission status: Accepted

Solution code:
N = int(input())
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
dp1 = [float('inf') for i in range(N+1)]
dp2 = [float('inf') for i in range(N+1)]
dp1[0] = 0
dp2[0] = 0
for i in range(1,N+1):
    for j in range(N+1):
        if dp1[j-1] <= HP[i-1][0]:
            dp2[j] = min(dp1[j],dp1[j-1]+HP[i-1][1])
        else:
            dp2[j] = dp1[j]
    dp1,dp2 =dp2,dp1
for i in range(N,-1,-1):
    if dp1[i] != float('inf'):
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    human = [tuple(map(int, input().split())) for _ in range(N)]

    human.sort(key = lambda x: (x[1]+x[0]))
    inf = 2000000001
    #iからj人乗せた中で最小座布団
    dp = [[inf]*(N+1) for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for j in range(N):
            if dp[i][j] <= human[i][0]:
                dp[i+1][j+1] = min(dp[i][j+1], dp[i][j] + human[i][1])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    ans = 0
    for i in range(N+1):
        if dp[N][i] != inf:
            ans = i

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
d = []
for i in range(N):
    h, p = map(int, input().split())
    d.append((h, p))

d = sorted(d, key=lambda x: x[0] + x[1])
INF = float('inf')
dp1 = [INF] * (N + 1)
dp2 = [INF] * (N + 1)
dp1[0] = 0
for i in range(1, N + 1):
    for j in range(N + 1):
        dp2[j] = dp1[j]
        if j == 0:
            continue
        if dp1[j - 1] > d[i - 1][0]:
            continue
        dp2[j] = min(dp2[j], dp1[j - 1] + d[i - 1][1])
    dp1, dp2 = dp2, dp1

for i in range(N, -1, -1):
    if dp1[i] < INF:
        print(i)
        exit()

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()
dp=[[10**13]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    s=A[i-1][1]
    t=A[i-1][2]
    for j in range(1,i+1):
        #print(A[i-1])
        if dp[i-1][j-1]>s:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+t)
for j in range(N,-1,-1):
    if dp[N][j]<10**13:
        print(j)
        break

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

# i人目まで考慮して、j人積んだ場合の積まれている高さの最小値
# 計算量削減のため、dp[j]=∞であるjのうち、最小のj以外は省略する
INF = float('inf')
dp = [0] + [INF]
lenDP = 2
num = 0
for i, (H, P) in enumerate(HPs, 1):
    iH = bisect_right(dp, H)
    x = lenDP - N + i - 2

    if x <= 0:
        dp0 = [0] + [hgt + P for hgt in dp[:iH]] + [INF] * (len(dp) - iH)
        dp = [x if x <= y else y for x, y in zip(dp0, dp)]
    else:
        # 最終的な答えに影響を与えなくなった要素を省略する
        dp0 = [hgt + P for hgt in dp[x-1:iH]] + [INF] * (len(dp) - iH)
        dp = [x if x <= y else y for x, y in zip(dp0, dp[x:])]
        lenDP -= x
        num += x

    if dp[-1] != INF:
        dp += [INF]
        lenDP += 1

print(num + len(dp) - 2)

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

# i人目まで考慮して、j人積んだ場合の積まれている高さの最小値
# 計算量削減のため、dp[j]=∞であるjのうち、最小のj以外は省略する
INF = float('inf')
dp = [0] + [INF]
for H, P in HPs:
    iH = bisect_right(dp, H)
    dp0 = [0] + [hgt + P for hgt in dp[:iH]] + [INF] * (len(dp) - iH)
    dp = [x if x <= y else y for x, y in zip(dp0, dp)]

    if dp[-1] != INF:
        dp += [INF]

print(len(dp) - 2)

Submission status: Accepted

Solution code:
n=input()
A=sorted(([int(e) for e in raw_input().split()] for _ in range(n)),key=lambda (x,y):x+y)
H=[0]
for (x,y) in A:
	for i in range(len(H)-1,-1,-1):
		if x>=H[i]:
			if i==len(H)-1: H.append(1e9)
			H[i+1]=min(H[i]+y,H[i+1])
print len(H)-1

Submission status: Accepted

Solution code:
inf = 1e18

N = int(raw_input())
HP = sorted([map(int, raw_input().split()) for i in xrange(N)], key = lambda x:x[0] + x[1])
dp =[inf] * 5005

for i in xrange(N):
    H, P = HP[i]
    for j in xrange(N + 1, -1, -1):
        if dp[j] < inf and dp[j] <= H:
            dp[j + 1] = min(dp[j + 1], dp[j] + P)
    dp[1] = min(dp[1], P)

ans = max(i for i in xrange(N + 1) if dp[i] < inf)

print ans