결국 답지를 또 봐야했던 문제.... for i in range(max_weight) max weight 이 백만이 될 수도 있었는데 이렇게 풀려했다니 나쁜 의미로 대단하다. 다시 풀어봐서 참 다행이다.

dict 쓰는법 {items(), values(), get(), update()}도 이문제 보면서 다시 짚을 수 있었다. 내일은 보석도둑 문제 풀어봐야겠다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

num_things, max_weight = map(int, input().split())

bag  = {0:0}

for _ in range(num_things):
    weight, value =  map(int, input().split())
    a = {}

    for w, v in bag.items():
        new_weight = weight + w
        new_value = value + v
# dict.get 함수는 weight key값에 맞는 value를 리턴해주고 만약 없다면 두번째 parameter 0 리턴
        if new_weight <= max_weight and new_value > bag.get(new_weight,0):
            a[new_weight] = new_value   
    bag.update(a)

print(max(bag.values()))