베시(암소)는 보석상에 가서 매력적인 팔찌를 훔치려고 한다. 당연히 N (1 ≤ N ≤ 3,402) 개 중에 가장 좋은 것으로 채우기를 원한다.

베시는 M (1 ≤ M ≤ 12,880)개의 무게까지 가져갈 수 있고, i 번째 팔찌는 Wi ( 1 <= Wi <= 400 )의 무게를 가진다. 또한 가지고 싶은 욕망도 Di ( 1 <= Di <= 100 )가 주어진다. 단, 각 팔찌는 한 개씩 있다.

가질 수 있는 무게와 각 팔찌의 무게와 욕망도가 주어질 때 최대 욕망도를 구하는게 문제이다.

입력

• 첫 줄은 팔찌 수 N 과 가져갈수 있는 최대 무게 M 이 주어진다.
• 다음 N 줄에는 각 무게와 욕망도가 주어진다.

출력

입출력 예

입력

4 6
1 4
2 6
3 12
2 7

출력

23

요구사항

-공간 복잡도: O(n)
-시간 복잡도: O(n^2)

출처: USACO 2007 December Silver