Going to the Movies

Farmer John is taking some of his cows to the movies! His truck can carry at most $C$ ($100 \le C \le 5000$) kilograms, and he wants to pick the group of cows whose combined weight is as large as possible without exceeding this limit $C$.

Given $N$ ($1 \le N \le 16$) cows and their weights $W_i$, determine the largest total weight of a group of cows that the truck can carry.

The first line contains two space-separated integers, $C$ and $N$.

Each of the next $N$ lines contains a single integer $W_i$, the weight of the $i$-th cow.

Print a single integer: the largest total weight of a group of cows that does not exceed $C$. If no cow can be taken, print $0$.