Going to the Movies

Interview

Time limit1sMemory limit128 MB

Summary

Given a truck capacity C and up to 16 cow weights, pick a subset whose total weight is as large as possible without exceeding C.

Level: Easy3 of 10
Topics: Brute force, Backtracking, Array, Recursion
Solved: No attempts yet

Problem

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.

Input

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.

Output

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$ .

Examples1

Example 1
Input
```
259 5
81
58
42
33
61
```
Expected output
```
242
```