문제
상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다.
두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다.
상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에, 노트북을 열고 사탕 가게의 시스템을 해킹하기 시작했다. 이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.
사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.
# 4781
import sys
input = lambda: sys.stdin.readline().strip()
n, m = map(float, input().split())
n, m = int(n), int(m * 100 + 0.5)
while n > 0:
candy = []
for _ in range(n):
c, p = map(float, input().split())
candy.append((int(c), int(p*100 + 0.5)))
candy.sort(key = lambda x:x[0], reverse = True)
candy.sort(key = lambda x:x[1])
knapsack = [0] * (m+1)
for c, p in candy:
for j in range(p, m+1):
knapsack[j] = max(knapsack[j], knapsack[j-p] + c)
print(knapsack[m])
n, m = map(float, input().split())
n, m = int(n), int(m * 100 + 0.5)