A smuggler's hold carries at most C units of weight. There are n item types; type i weighs w_i each, is worth v_i each, and only c_i copies are available. Choose how many of each type to pack (from 0 up to c_i) so the total weight is at most C and the total value is maximized. Report that maximum value (0 if nothing fits).
Input format
Line 1: two integers n and C.
Next n lines: three integers w_i, v_i and c_i for each item type.
Output format
A single integer: the maximum total value for total weight at most C.
Constraints
- 1 <= n <= 40
- 0 <= C <= 2000
- 1 <= w_i <= 1000
- 1 <= v_i <= 1000
- 1 <= c_i <= 50