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):
"""
余裕の小さい人から先に座布団を積ませた方がよい。
余裕の大きさは自分の身長と他人のパワーで決まる。
いまここにAとBがいる。
このとき、Bp > AhならAが先に積んだ方がよい。
Ap > Bh ならBが先に積んだ方がよい。
これは書き換えるとAh - Bp < 0ならAがさき、Bh - Ap < 0ならBが先。
Ah - Bp < Bh - ApならAが先、Ah - Bp > Bh - ApならBが先である。
書き換えると、
Ah + Ap < Bh + Bp ならAが先、Ah + Ap > Bh + Bp ならBが先である。
したがって身長+パワーで昇順に並び替えればよい。
"""
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key= lambda x:x[0]+x[1])
dp = [float("INF")]*(N+1)
dp[0] = 0
for i in range(N):
    h,p = HP[i]
    for j in range(N,0,-1):
        if dp[j-1] <= h:
            dp[j] = min(dp[j],dp[j-1]+p)

for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
hp = [tuple(map(int, input().split())) for _ in range(n)]
hp.sort(key=lambda x: x[0]+x[1])
dp = [10**15] * (n+1)
dp[0] = 0
for i in range(n):
    h,p = hp[i]
    for j in range(n,0,-1):
        if dp[j-1]<=h:
            dp[j] = min(dp[j], dp[j-1]+p)

for i in range(n, -1, -1):
    if dp[i]<10**15:
        break
ans = i
print(ans)

Solution (Python):
"""
Aさん：身長Ha , パワーPa
Bさん：身長Hb , パワーPb
二人どちらも積めるのに順番を間違えたばかりに一人しか積めない、という事態を避けたい。
Aさんが先に積むべき？Bさんが先に積むべき？
Aさん、Bさんの手前までの時点で高さSまで積みあがっているとする。S <= min(Hb,Ha)とする。

S+Pa > Hb　かつ S+Pb <= HaならBが先
S+Pb > Ha　かつ S+Pa <= HbならAが先

Pa-Hb > Pb-Ha ならBが先でAが後
書き換えるとPa+Ha > Pb+HbならBが先でAが後
つまり、P+H順にソートしてナップサックすればよい
"""


N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key = lambda x:x[0]+x[1])

dp = [float("INF")]*(N+1)
dp[0] = 0
for h,p in HP:
    for j in range(N,0,-1):
        if dp[j-1] <= h:
            dp[j] = min(dp[j],dp[j-1]+p)

for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Solution (Python):
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [float("INF")]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(N,0,-1):
        if dp[j-1] <= HP[i-1][0]:
            dp[j] = min(dp[j],dp[j-1]+HP[i-1][1])
for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Solution (Python):
import bisect

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

hito.sort()
data=[0]
for i in range(0,N):
    gomi,h,p=hito[i]
    for j in range(len(data)-1,-1,-1):
        if j==len(data)-1:
            if h>=data[-1]:
                data.append(data[-1]+p)
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
        else:
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
    

print(len(data)-1)

Solution (Python):
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
ceil = max(HP,key=lambda x: x[0])[0]

dp = [[ceil+1]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    h,p = HP[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1]<=h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
            ans = max(ans,j)
        else:
            dp[i][j] = dp[i-1][j]

print(ans)

Solution (Python):

"""
https://atcoder.jp/contests/cf17-final/tasks/cf17_final_d

全て置けるかの判定を考える
H+Pで昇順ソート
後ろから見ていって、その時点での座布団がH+P以下なら○　だめならX
を付けてPを引く
を繰り返し、全て○なら全員置ける(丸の数以上の答えであることが確定する)

あとは前から見ていってdp?
dp[i][j] = i人目まで見てj人置いた時の最小の枚数
→H+Pでソートするのが正しいなら絶対おｋなんだが…

"""

N = int(input())

SHP = []

for i in range(N):

    h,p = map(int,input().split())
    SHP.append( (h+p,h,p) )

SHP.sort()

dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(N):

    s,h,p = SHP[i]

    for j in range(N-1,-1,-1):

        if dp[j] <= h:
            dp[j+1] = min(dp[j+1] , dp[j] + p)

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

Solution (Python):
n = int(input())
hp = [list(map(int,input().split())) for i in range(n)]
hp.sort(key = lambda x:x[0]+x[1])
dp = [[10**18 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  h,p = hp[i-1]
  for j in range(i+1):
    if j < i:
      dp[i][j] = dp[i-1][j]
    if j and dp[i-1][j-1] <= h:
      dp[i][j] = min(dp[i][j],dp[i-1][j-1]+p)
for i in range(n+1):
  if dp[-1][i] == 10**18:
    print(i-1)
    break
else:
  print(n)

Solution (Python):
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1

dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break

Solution (Python):
N = int(input())
HP = [tuple(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: sum(x))

INF = float('inf')
dp = [0]
maxj = 0
for i,(h,p) in enumerate(HP):
	dp2 = [INF] * (maxj + 2)
	for j in range(maxj,-1,-1):
		dp2[j] = min(dp2[j], dp[j])
		if dp[j] <= h:
			dp2[j+1] = min(dp2[j+1], dp[j] + p)
			if j == maxj:
				maxj += 1
	dp = dp2
print(maxj)

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [tuple(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
	for j in range(i+1, 0, -1):
		if dp[j-1] <= men[i][0]:
			dp[j] = min(dp[j], dp[j-1] + men[i][1])


for i in range(n+1):
	if dp[i] < INF:
		ans = i
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp += [INF]
    for j in range(i+1, 0, -1):
        if dp[j-1] > hi:
            continue
        dp[j] = min(dp[j], dp[j-1]+pi)
for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)

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


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

for i in range(N):
  _,h,p = A[i]
  for j in range(N, 0, -1):
    
    if dp[j-1] < 0:
      continue
    
    if dp[j-1] > h:
      continue
    if dp[j] < 0:
      dp[j] = dp[j-1] + p
    else:
      dp[j] = min(dp[j], dp[j-1] + p)
    
for i in range(N+1):
  if dp[i] < 0:
    print(i-1)
    exit(0)

print(N)

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    N = int(input())
    HP = []
    for i in range(N):
        h, p = map(int, input().split())
        HP.append((h, p, h+p))
    HP.sort(key=itemgetter(2))

    inf = 10**15
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        h, p, _ = HP[i]
        for j in range(N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j+1 <= N:
                if h >= dp[i][j]:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p)
    for i in range(N, -1, -1):
        if dp[-1][i] < inf:
            print(i)
            break


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
M = []
for _ in range(N):
    h, p = map(int, input().split())
    M.append((h, p))
M = sorted(M, key=lambda x: x[0] + x[1])
dp = [10 ** 9 + 1] * (N+1)
dp[0] = 0
ans = 0
for h, p in M:
    for i in range(N-1, -1, -1):
        if dp[i] <= h:
            dp[i+1] = min(dp[i+1], dp[i] + p)
            ans = max(ans, i+1)

print(ans)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
H,P = np.array([[int(x) for x in input().split()] for _ in range(N)],dtype=np.int64).T

i = (H+P).argsort()
H = H[i]; P = P[i]


INF = 10**18
dp = np.full(N+1,INF,dtype=np.int64)
dp[0] = 0
for h,p in zip(H,P):
    prev = dp
    dp = prev.copy()
    can_add = (prev[:-1] <= h)
    np.minimum(dp[1:], np.where(can_add, prev[:-1]+p, INF), out=dp[1:])

answer = np.where(dp < INF)[0][-1]
print(answer)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

INF = 10 ** 18

N = input()

ls = []
for i in range(N):
    H, P = map(int, raw_input().split())
    ls.append((H + P, H, P))

ls.sort()

DP = [INF] * (N + 1)
DP[0] = 0

for i in range(N):
    _, H, P = ls[i]
    for j in range(i, -1, -1):
        if DP[j] <= H and DP[j + 1] > DP[j] + P:
            DP[j + 1] = DP[j] + P

ans = 0
for i in range(N + 1):
    if DP[i] < INF:
        ans = i

print ans

Solution (Python):
from bisect import*
N = int(input())
P = []

for i in range(N):
    h, p = map(int, input().split())
    P.append((h+p, h, p))
P.sort()

dp = [10**18]*(N+1)
dp[0] = 0
for i in range(N):
    k, h, p = P[i]
    idx = bisect(dp, h)
    for j in range(idx-1, -1, -1):
        dp[j+1] = min(dp[j]+p, dp[j+1])
    
    
print(bisect(dp, 10**17)-1)