Knapsack#4831
Find the maximum weight of gold that can be carried in a knapsack with a capacity of , if gold bars are given with specified weights.
The first line contains one number (1 \le s \le 10^4) — the knapsack capacity. Then follow (1 \le n \le 300) non-negative integers, not exceeding 10^5 — the weights of bars.
Print the maximum weight of gold that can be carried in the knapsack.
Example 1
Example 2