The Eating Puzzle

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 21 bucket sizes and a calorie limit, choose a subset with the largest sum that does not exceed the limit.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation, Array, Recursion
Solved: No attempts yet

Problem

Bessie is on a diet and may eat no more than $C$ ( $10 \le C \le 35000$ ) calories per day. To tease her, Farmer John sets out $B$ ( $1 \le B \le 21$ ) buckets of feed, each holding some number of calories (each value is between $1$ and $35000$ , and the values need not be distinct). Bessie has no self-control: once she starts on a bucket, she eats all of it.

Bessie is not good at combinatorics. Determine the combination of feed buckets that lets her eat as many calories as possible without exceeding the limit $C$ , and report that number of calories.

Input

Line 1: Two space-separated integers, $C$ and $B$ .
Line 2: $B$ space-separated integers giving the calories in bucket 1, bucket 2, and so on.

Output

Line 1: A single integer — the largest number of calories Bessie can consume while staying on her diet.

Examples1

Example 1
Input
```
40 6
7 13 17 19 29 31
```
Expected output
```
39
```