import sys
input = sys.stdin.readline
from collections import deque
N,K = map(int,input().split())
WV = []
dq = deque()
for i in range(N):
WV.append(list(map(int,input().split())))
DP = [[0]*(K+1) for i in range(N+1)]
for i in range(1,N+1):
w,v = WV[i-1]
for weight in range(1,K+1):
if weight < w:
DP[i][weight] = DP[i-1][weight]
else:
DP[i][weight] = max(DP[i-1][weight-w]+v,DP[i-1][weight])
print(DP[N][K])
무려 일주일 넘게 끙끙대면서 풀지 못했던 문제다.
답지 안보고 풀려고 애쓰다가 결국은 답지를 보고 말았는데, "냅색(Knapsack) 알고리즘"의 전형적인 문제였다.
이런 문제는 생각한다고 생각할 수 있는 문제가 아니기 때문에 본인이 천재가 아니라면 아이디어를 떠올리는 것보다는 공부하는것이 맞을 것이다.
오늘의 교훈) 안풀리는 문제를 너무 오래 붙들고 있지 말자