Find the maximum weight of gold that can be carried in a knapsack with a capacity of s, if n gold bars are given with specified weights.
The first line contains one number s(1≤s≤104) — the knapsack capacity. Then given n(1≤n≤300) non-negative integers, not exceeding 105 — the weights of bars.
Print the maximum weight of gold that can be carried in the knapsack.