Ordinary Knapsack 2

Interview

Time limit1sMemory limit512 MB

Summary

Given N item types with weight, satisfaction, and a copy count, choose a multiset whose total weight is at most M and whose total satisfaction is largest.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Binary search, Implementation
Solved: No attempts yet

Problem

This is the second problem about a very ordinary knapsack.

Minho is packing a bag for a camp. His satisfaction depends on which items go into the bag. Putting every item at home into the bag would give him the most satisfaction, but the bag has a fixed weight limit and he cannot pack past that limit.

The house can hold several copies of the same item, so he may pack two or more of one kind. An item cannot be split, and each kind can be packed at most as many times as there are copies at home.

Find the case where Minho feels the most satisfaction.

Input

The first line contains N and M separated by a space ( $1 \le N \le 100$ , $1 \le M \le 10000$ ). N is the number of item kinds at Minho's house and M is the maximum bag weight Minho can carry.

Each of the next N lines describes one kind of item at the house, one kind per line. Each line holds V, C, K ( $1 \le V \le M$ , $1 \le C, K \le 10000$ , $1 \le V \times K \le 10000$ ). V is the weight of one copy, C is the satisfaction Minho gains when one copy goes into the bag, and K is the number of copies at the house.

Output

Print on one line the largest satisfaction Minho can feel when the packed items do not exceed the maximum weight.

Examples7

Example 1
Input
```
2 3
2 7 1
1 9 3
```
Expected output
```
27
```
Example 2
Input
```
3 9
8 5 1
1 2 2
9 4 1
```
Expected output
```
7
```
Example 3
Input
```
1 1
1 1 1
```
Expected output
```
1
```
Example 4
Input
```
1 10
3 4 2
```
Expected output
```
8
```
Example 5
Input
```
1 10
5 6 100
```
Expected output
```
12
```
Example 6
Input
```
3 10
6 11 1
5 7 2
4 6 1
```
Expected output
```
17
```
Example 7
Input
```
3 7
7 5 3
7 9 1
7 2 5
```
Expected output
```
9
```