한 아이템 중복 사용을 막기 위해 역방향으로, 중복 사용 가능 시 정방향!
dp[w]: 가방의 무게가 w일때 가질 수 있는 최대 가치- 점화식: dp[w] = max(dp[w],
dp[w - weights[i]] + values[i])
n, k = map(int, input().split())
weights = []
values = []
for _ in range(n):
w, v = map(int, input().split())
weights.append(w)
values.append(v)
# dp[w]: 가방의 무게가 w일때 가질 수 있는 최대 가치
dp = [0] * (k + 1)
for i in range(n):
# 한 아이템 중복 사용을 막기 위해 역방향으로, 중복 사용 가능 시 정방향!
for w in range(k, weights[i] - 1, -1):
# 기존 dp[w](아이템 i를 넣지 않는 경우)와 아이템 i를 넣는 경우 중 가치가 더 큰 경우를 채택
# dp[w - weights[i]] : 현재 물건을 넣으려면 무게가 weight[i]만큼 필요하므로, 그만큼 남은 공간에서 얻을 수 있는 최대 가치
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
print(dp[k])
