Competitions
Huseyn and knapsack
Knapsack
Find the maximum weight of gold that can be carried out in a knapsack of capacity s, if there are n gold ingots with specified weights.
Input data
The first line contains one number s (1 ≤ s ≤ 10^4). Then given n (1 ≤ n ≤ 300) non-negative integers, not exceeding 10^5 - the weights of ingots.
Output data
Print the desired maximum weight.
Examples
Input example #1
10 1 4 8
Output example #1
9
Input example #2
20 5 7 12 18
Output example #2
19