You are packing for a trek. There are n items; item i weighs w[i] kg and is worth v[i] points. Your bag holds at most W kg. Each item can be taken at most once.
Print the largest total value you can carry.
Constraints
- 1 ≤ n ≤ 1000
- 1 ≤ W ≤ 10000
- 1 ≤ w[i] ≤ 10000, 1 ≤ v[i] ≤ 10^6
Input and output
- Input
- Line 1: n and W. Line 2: n weights. Line 3: n values.
- Output
- One integer.
Examples
Input 1
4 7
1 3 4 5
1 4 5 7Output
9Take the items weighing 3 and 4: weight 7, value 4 + 5 = 9.
Input 2
2 1
2 3
10 20Output
0Nothing fits in a bag of capacity 1, so 0.
Show hints
- best[c] = the best value with capacity c using the items seen so far.
- Sweep c downwards so an item is not used twice.
Show the explanation
Keep best[c] for every capacity 0..W. For each item, update best[c] = max(best[c], best[c − w] + v) for c from W down to w. Going downwards matters: best[c − w] still describes the state before this item, so each item is used at most once. (Going upwards gives the unlimited-supply version.) The answer is best[W].
Original UniCircle question. Last reviewed 22 Oct 2026.