페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1077

배낭채우기1 1s 64MB

문제

정올 보석상에 도둑이 침입했다. 도둑은 배낭에 보석을 훔치려고 한다. 

이때, 훔친 보석의 무게가 W를 넘어가면 배낭이 망가진다.

각 보석의 값어치와 무게가 주어질 때, 도둑은 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되도록 보석을 배낭에 담으려고 한다. 

이때 배낭에 담을 수 있는 최대 값어치를 구하시오.


입력

첫 줄은 보석의 가지 수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 둘째 줄부터 N+1줄에는 각 보석의 무게 W_i(1≤W_i≤W)와 값어치 P_i가 주어진다.

(단, 각각의 보석의 개수는 무제한으로 가정한다.)


출력

보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서, 보석의 총 값어치가 최대가 되는 최대값을 출력한다.

최대값은 int 범위 이내이다.


예제 

4 14 

2 40 

5 110 

10 200 

3 50
300


로그인해야 코드를 작성할 수 있어요.