탐험가의 배낭에는 무게 W까지만 담을 수 있어요. 보물이 N개 있고, 각 보물은 무게와 가치가 있어요. 보물은 쪼갤 수 없고, 각각 담거나 안 담거나 둘 중 하나예요. 배낭에 담을 수 있는 보물 가치의 최댓값을 구하세요.
입력
첫째 줄에 보물 수 N과 배낭 용량 W가 주어져요. (1 ≤ N ≤ 100, 1 ≤ W ≤ 10,000) 다음 N개의 줄에 각 보물의 무게와 가치가 공백으로 구분되어 주어져요. (1 ≤ 무게, 가치 ≤ 1,000)
출력
담을 수 있는 가치의 최댓값을 출력해요.