> 문제 <

출처 : https://www.acmicpc.net/problem/12865

> 아이디어 <

dp[현재 물건][현재 가방 무게]

현재 돌고있는 배낭무게(j)가 현재 물건의 무게(w)보다 작다면
배낭에 넣을 수 없으므로 dp[i][j] = dp[i-1][j] 이전물건가방의 가치를 가져온다

else 작거나 같다면,
1. 현재 물건(w)을 넣어주고 남은 무게를 채우는 dp[i-1][j-w] + v(가치) <남은 무게 index의 가치 + 현 가치>
2. 현재 물건을 넣지않고 이전물건으로만 채우는 dp[i-1][j]

1과 2중 큰것을 dp[i][j]에 넣어주기

아이디어 출처 : https://suri78.tistory.com/2

> 코드 <

import sys
input = lambda: sys.stdin.readline()

n,k = map(int, input().split())
dp=[[0 for _ in range(k+1)] for _ in range(n+1)]

wvlist = [[0,0]]
for _ in range(n):
  wvlist.append(list(map(int, input().split())))

for i in range(1,n+1):
  for j in range(1, k+1):
    w = wvlist[i][0]
    v = wvlist[i][1]

    if j < w:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(v+dp[i-1][j-w], dp[i-1][j])

print(dp[n][k])