For the "treasure bag" round, players choose items (each with a weight and value) to maximize total value without exceeding the bag's weight limit, and each item can only be picked once. Given N items with weights and values, and knapsack capacity W, find the maximum total value without exceeding W, where each item can be used at most once.
Input
Line1: N W. Next N lines: weight value.
Output
Maximum value.
Constraints
1 ≤ N ≤ 500, 1 ≤ W ≤ 10^4
Sample Input
3 50 10 60 20 100 30 120
Sample Output
220
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.