Limited Stock Knapsack

Difficulty: 1900 6000 ms 128 MB

dp

Each item i has weight w_i, value v_i, and is available at most c_i times. Maximize value within capacity W.

Input: the first line has N and W; each of the next N lines has w_i v_i c_i.

Output: the maximum achievable value.

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 10⁴
• 1 ≤ c_i ≤ 1000

Sample Tests

2 5
2 3 2
3 4 1

7

1 4
2 5 3

10

Read the Editorial