평범한 배낭 2

면접 대비

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

요약

무게, 만족도, 개수가 정해진 N가지 물건에서 총 무게가 M을 넘지 않도록 물건을 골라 만족도의 합을 최대로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

아주 평범한 배낭을 다루는 두 번째 문제다.

민호는 캠프에 가려고 가방을 싼다. 가방에 어떤 물건을 넣는지에 따라 민호의 만족도가 달라진다. 집에 있는 물건을 모두 넣으면 만족도가 가장 커지지만, 민호가 들 수 있는 가방의 무게가 정해져 있어서 그 무게를 넘기도록 담을 수는 없다.

집에는 같은 물건이 여러 개 있을 수 있어서 한 종류를 두 개 이상 담는 것도 가능하다. 물건은 쪼갤 수 없고, 각 종류는 집에 있는 개수까지만 담을 수 있다.

민호가 만족도를 가장 크게 느낄 수 있는 경우를 찾아보자.

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어진다 ( $1 \le N \le 100$ , $1 \le M \le 10000$ ). N은 민호의 집에 있는 물건의 종류 수이고, M은 민호가 들 수 있는 가방의 최대 무게다.

둘째 줄부터 N개의 줄에 걸쳐 집에 있는 물건의 정보가 한 줄에 하나씩 주어진다. 각 줄은 V, C, K로 이루어진다 ( $1 \le V \le M$ , $1 \le C, K \le 10000$ , $1 \le V \times K \le 10000$ ). V는 물건 하나의 무게, C는 그 물건 하나를 가방에 넣을 때 올라가는 만족도, K는 집에 있는 그 물건의 개수다.

출력

최대 무게를 넘기지 않게 물건을 담았을 때 민호가 느낄 수 있는 만족도의 최댓값을 한 줄에 출력한다.

예제7

예제 1
입력
```
2 3
2 7 1
1 9 3
```
예상 출력
```
27
```
예제 2
입력
```
3 9
8 5 1
1 2 2
9 4 1
```
예상 출력
```
7
```
예제 3
입력
```
1 1
1 1 1
```
예상 출력
```
1
```
예제 4
입력
```
1 10
3 4 2
```
예상 출력
```
8
```
예제 5
입력
```
1 10
5 6 100
```
예상 출력
```
12
```
예제 6
입력
```
3 10
6 11 1
5 7 2
4 6 1
```
예상 출력
```
17
```
예제 7
입력
```
3 7
7 5 3
7 9 1
7 2 5
```
예상 출력
```
9
```