Time Limit: 10s
Memory Limit: 128MB
유나는 보석 가게에서 목걸이들에 대해 알아보았습니다. 그녀는 N(1~3402)개의 목걸이 중에서 가능한 가장 매력적인 목걸이를 사고 싶어 합니다. 각각의 목걸이는 Wi(1~400)만큼의 무게를 가지고 있으며, Di(1~100)만큼의 매력 수치를 가지고 있으며, 모든 목걸이는 한개만 남은 한정판입니다. 유나는 M(1~12,880)만큼의 무게 제한 이내에서 살 수 있는 가장 최적의 목걸이 집합을 찾고 싶습니다.
무게 제한이 주어졌을 때, 살 수 있는 목걸이 집합이 가질 수 있는 가장 높은 매력 수치의 합을 알려주십시오!
* Line 1 : 2개의 정수, N, M*
- N : 목걸이의 개수
- M* : 무게 제한
* Line 2 ~ N+1 : 2개의 정수 Wi, Di
- Wi : 목걸이의 무게
- Di : 목걸이의 매력 수치
* Line 1 : 목걸이 집합이 갖는 매력 수치의 합을 적습니다. 목걸이 집합의 무게의 합은 무게 제한을 넘을 수 없습니다.
4 6 1 4 2 6 3 12 2 7
23