백준 12865번(python)

---

N, K = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

weights = [ele[0] for ele in wv]
values = [ele[1] for ele in wv]

dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, K+1):
        w = weights[i-1]
        v = values[i-1]
        
        # 먼저, 가질 수 있는 무게보다 물건의 무게가 클 경우는
        # 가져갈 수 없으므로 이전에 구했던 최댓값을 선택한다.
        # 여기서 i-1이 이전에 구했던 것이고, j가 가질 수 있는 무게를 의미한다.
        if(j < w):
            dp[i][j] = dp[i-1][j]
        # 물건의 무게보다 가질 수 있는 무게가 더 작을 경우는
        # 해당 물건을 가져갈 수 있음을 의미한다.
        # 따라서 v + dp[i-1][j-w]
        # --> 현재 물건을 가져감(v)과 동시에
        # 이전에 미리 구해둔 해당 물건의 무게만큼을 제외했을 때의 최댓값과(dp[i-1][j-w])
        # 이전에 구했던 무게를 비교하여 선택한다.(안가져가는게 이득일 수도 있으니까)
        else:
            dp[i][j] = max(v + dp[i-1][j - w], dp[i-1][j])
print(dp[N][K])