어느 날, 골드는 보안이 허술한 보석상에 침입했습니다. 보석상에는 총 N 종류의 보석들이 진열되어 있습니다.

각 보석은 저마다의 무게 w_i와 가치 v_i를 가지고 있습니다.

보석상에는 각 종류의 보석이 무한히 많이 쌓여 있어서, 골드는 가방이 버틸 수만 있다면 같은 종류의 보석을 몇 개든 원하는 만큼 가방에 담을 수 있습니다.

골드가 가져간 배낭은 최대 W만큼의 무게를 버틸 수 있습니다.

골드가 가방에 담은 보석들의 총 무게가 W를 넘지 않으면서, 가방에 담긴 보석들의 총 가치의 합을 최대화하는 프로그램을 작성하시오.

입력

첫째 줄에 보석의 종류 N과 배낭이 버틸 수 있는 최대 무게 W가 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 보석의 무게 w_i와 가치 v_i가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 골드가 가방에 담을 수 있는 보석의 최대 가치 합을 출력한다.

제한 사항

• 1 ≤ N ≤ 1,000
• 1 ≤ W ≤ 10,000
• 1 ≤ w_i ≤ W
• 1 ≤ v_i ≤ 1,000,000

예제 입력 1

3 10
2 5
3 9
4 11

예제 출력 1

29