참 팔찌

면접 대비

시간 제한1초메모리 제한128 MB

요약

무게와 만족도가 정해진 N개의 장식을 중복 없이 골라, 총 무게가 M을 넘지 않으면서 만족도의 합이 최대가 되도록 한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

베시(Bessie)가 쇼핑몰의 보석 가게에서 참 팔찌를 발견했다. 베시는 판매 중인 $N$ 개( $1 \le N \le 3402$ )의 장식(charm) 중에서 가장 좋은 조합을 골라 팔찌를 채우고 싶다. 각 장식 $i$ 는 무게 $W_i$ ( $1 \le W_i \le 400$ )와 매력도 $D_i$ ( $1 \le D_i \le 100$ )를 가지며, 각 장식은 최대 한 번만 사용할 수 있다. 팔찌가 감당할 수 있는 총 무게는 $M$ ( $1 \le M \le 12880$ ) 이하이다.

무게 제한과 장식들의 목록(무게와 매력도)이 주어질 때, 얻을 수 있는 매력도의 최대 합을 구하여라.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $M$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에는 장식 $i$ 의 무게 $W_i$ 와 매력도 $D_i$ 가 공백으로 구분되어 주어진다.

출력

무게 제한을 넘지 않으면서 얻을 수 있는 매력도 합의 최댓값을 정수 하나로 출력한다.

힌트

예시에서는 두 번째 장식을 제외하는 것이 최적이다. 무게가 각각 $1$ , $3$ , $2$ 인 장식을 선택하면 매력도가 $4 + 12 + 7 = 23$ 이 되고, 총 무게는 $1 + 3 + 2 = 6$ 으로 제한을 넘지 않는다.

예제3

예제 1
입력
```
4 6
1 4
2 6
3 12
2 7
```
예상 출력
```
23
```
예제 2
입력
```
1 1
1 100
```
예상 출력
```
100
```
예제 3
입력
```
1 5
6 42
```
예상 출력
```
0
```