Knapsack

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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.

Input

The first line contains one number $s (1 \leq s \leq 1 0^{4})$ — the knapsack capacity. Then given $n (1 \leq n \leq 300)$ non-negative integers, not exceeding $1 0^{5}$ — the weights of bars.

Output

Print the maximum weight of gold that can be carried in the knapsack.

Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 6K

Acceptance rate 30%