# 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≤s≤10_{4})$ — the knapsack capacity. Then given $n(1≤n≤300)$ non-negative integers, not exceeding $10_{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 29%