(DP) 백준 12865번 평범한 배낭

import sys 
N, K = map(int, sys.stdin.readline().split()) 
item = [[0, 0]] 
for i in range(1, N + 1): 
	item.append(list(map(int, sys.stdin.readline().split()))) 
    
dp = [[0] * (K + 1) for _ in range(N + 1)] # 물건의 개수 * 0~7까지의 최대 무게의 배열

for i in range(1, N + 1): # 요소 하나하나를 검사하면서
	for j in range(1, K + 1): 
    	if j >= item[i][0]: # 만약에 물건의 무게보다 배낭의 무게가 크다면 (즉, 물건을 배낭에 넣을 수 있다면)
              dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1]) # dp는 
              #이전까지의 최댓값과 최대 무게에서 현재 물건의 무게를 빼고 나머지 무게를 더한 값 중에 최대 값을 비교해서 넣는다. 
              #무게가 7이고 현재 물건의 무게가 4일경우 7-4=3이 되어 물건 3의 지점의 최대 값이 더해지게 된다.
              
        else: 
              dp[i][j] = dp[i-1][j] # 현재 물건의 무게가 최대 무게보다 클 경우 전 단계의 무게를 가져온다.
            
print(dp[N][K])