Baekjoon-12865-평범한 배낭

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
Ws,Vs = [],[]
for _ in range(N):
    w,v = map(int, input().split())
    Ws.append(w)
    Vs.append(v)

# O(NK) 가능
dp = [-1 for _ in range(K+1)]
dp[0] = 0
for n in range(N):
    W,V = Ws[n], Vs[n]
    for k in range(K,-1,-1):
        if k-W >= 0 and dp[k-W] != -1:
            dp[k] = max(dp[k], dp[k-W]+V)

print(max(dp))

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
Ws,Vs = [],[]
for _ in range(N):
    w,v = map(int, input().split())
    Ws.append(w)
    Vs.append(v)

# O(NK) 가능
dp = {0:0}
for n in range(N):
    W,V = Ws[n], Vs[n]
    cache = {}
    for key in dp.keys():
        if key+W < K+1:
            cache[key+W] = max(dp[key] + V, dp.get(key+W,0))
    dp.update(cache)

print(max(dp.values()))