배낭 채우기

첫 줄에 물건의 개수 n (1 이상 100 이하) 과 배낭이 버티는 무게 W (1 이상 10000 이하) 가 주어집니다. 이어서 n개의 줄에 각 물건의 무게와 가치가 주어집니다. 무게와 가치는 1 이상 1000 이하입니다.

무게의 합이 W 를 넘지 않게 물건을 고를 때 (각 물건은 한 번만 담을 수 있습니다), 담은 물건들의 가치 합의 최댓값을 출력하세요.

예시

입력

4 7
6 13
4 8
3 6
5 12

출력

14