가방 문제 (냅색 알고리즘)

"""
최고 17kg의 무게를 저장할 수 있는 가방이 있다.
그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.
이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.
이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치
한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다.

가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

첫 번째 줄은 보석 종류의 개수, 가방에 담을 수 있는 무게의 한계값
두 번째 줄부터 각 보석의 무게와 가치

4 11
5 12
3 8
6 14
4 8


"""
import sys
input=sys.stdin.readline

n,m=map(int, input().split())
d=[0]*(m+1)

for i in range(n):
    w,v=map(int,input().split())

    # 현재 적용하고자 하는 보석의 무게부터
    for j in range(w, m+1):
        # j-w : w만큼 무게를 담는다고 가정했을 때, w무게만큼 갖는 보석을 담기위해 무게 비워놓고 빈공간 마련해둠
        d[j]=max(d[j], d[j-w]+v)

print(d)
print(d[m])