Unlimited Supplies

Difficulty: 1600 3000 ms 128 MB

dp

Same knapsack, but every item is available in unlimited quantity. Maximize the value within capacity W.

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

Output: the maximum total value with repetition allowed.

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 1000
• 1 ≤ w_i ≤ 1000
• 0 ≤ v_i ≤ 10⁴

Sample Tests

2 8
3 30
5 60

90

1 3
2 5

5

Read the Editorial