10043 01 배낭 문제 Gold V

문제

N개의 물건이 있고, 각 물건은 무게 W와 가치 V를 가진다. 배낭의 최대 용량이 K일 때, 배낭에 넣을 수 있는 물건들의 가치의 합의 최댓값을 구하는 프로그램을 작성하시오. 각 물건은 하나씩만 있다.

입력

첫째 줄에 물건의 수 N (1 ≤ N ≤ 100)과 배낭의 최대 용량 K (1 ≤ K ≤ 10,000)가 주어진다. 둘째 줄부터 N개의 줄에 각 물건의 무게 W와 가치 V가 주어진다. (1 ≤ W ≤ K, 1 ≤ V ≤ 1,000)

출력

배낭에 넣을 수 있는 물건들의 가치의 합의 최댓값을 출력한다.

4 7
6 13
4 8
3 6
5 12

14