Description
Problem Introduction
You are given a set of bars of gold and your goal is to take as much gold as possible into your bag.
There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).
Problem Description
Task.
Given n gold bars, find the maximum weight of gold that fits into a bag of capacity W.
Input Format.
The 1st line of the input contains the capacity W of a knapsack and the number n of bars of gold.
The 2nd line contains n integers W0, ..., Wn−1 defining the weights of the bars of gold.
Constraints.
1 ≤ W ≤ 10^4;
1 ≤ n ≤ 300;
0 ≤ W0, ..., Wn−1 ≤ 10^5
Output Format.
Output the maximum weight of gold that fits into a knapsack of capacity W
E.g. 1,
Input:
10 3
148
Output: 9
Here, the sum of the weights of the first and the last bar is equal to 9.