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

Solution (Python):
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

Solution (Python):
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
    
    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()

Solution (Python):
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()

Solution (Python):
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):
        
        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

Solution (Python):
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])



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)

Solution (Python):
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])



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)

Solution (Python):
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

Solution (Python):
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()))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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