eolymp
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

The first line contains one number s (1s104). Then given n (1n300) non-negative integers, not exceeding 105 - the weights of ingots.

Output

Print the desired maximum weight.

prb4831.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
10
1 4 8
Output example #1
9
Input example #2
20
5 7 12 18
Output example #2
19