1371 - 매혹의 목걸이

Time Limit: 10s Memory Limit: 128MB

Submissions: 108 Solved: 29
Description

유나는 보석 가게에서 목걸이들에 대해 알아보았습니다. 그녀는 N(1~3402)개의 목걸이 중에서 가능한 가장 매력적인 목걸이를 사고 싶어 합니다. 각각의 목걸이는 Wi(1~400)만큼의 무게를 가지고 있으며, Di(1~100)만큼의 매력 수치를 가지고 있으며, 모든 목걸이는 한개만 남은 한정판입니다. 유나는 M(1~12,880)만큼의 무게 제한 이내에서 살 수 있는 가장 최적의 목걸이 집합을 찾고 싶습니다.

무게 제한이 주어졌을 때, 살 수 있는 목걸이 집합이 가질 수 있는 가장 높은 매력 수치의 합을 알려주십시오!

Input

* Line 1  : 2개의 정수, N, M*

    - N : 목걸이의 개수

    - M* : 무게 제한

* Line 2 ~ N+1 : 2개의 정수 Wi, Di

    - Wi : 목걸이의 무게

    - Di : 목걸이의 매력 수치

Output

* Line 1 : 목걸이 집합이 갖는 매력 수치의 합을 적습니다. 목걸이 집합의 무게의 합은 무게 제한을 넘을 수 없습니다.

Sample Input
4 6
1 4
2 6
3 12
2 7
Sample Output
23