10085 평범한 배낭 Gold V

문제

N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가진다. 배낭의 최대 용량이 K일 때, 가치의 합의 최댓값을 구하시오. 각 물건은 최대 1개 넣을 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 K (1 ≤ K ≤ 100,000)가 주어진다. 다음 N개의 줄에 W, V가 주어진다. (1 ≤ W ≤ 100,000, 0 ≤ V ≤ 1,000)

출력

가치의 합의 최댓값을 출력한다.

4 7
6 13
4 8
3 6
5 12

14