Hay For Sale

Interview

Time limit1sMemory limit128 MB

Summary

Given a wagon capacity and a list of hay bale volumes, find the largest total volume not exceeding the capacity that can be formed by choosing whole bales.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Binary search, Brute force
Solved: No attempts yet

Problem

Farmer John suffered a terrible loss when a swarm of giant Australian cockroaches ate his entire hay inventory, leaving nothing to feed the cows. To get some hay before the cows miss a meal, he hitched up a wagon with capacity $C$ cubic units ( $1 \le C \le 50{,}000$ ) and set off for Farmer Don's.

Farmer Don has $H$ different hay bales for sale ( $1 \le H \le 5{,}000$ ), each with its own volume $V_i$ ( $1 \le V_i \le C$ ). Bales of hay, as you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.

FJ carefully weighs the volumes so he can figure out the largest amount of hay he can buy for his cows.

Given the capacity limit and the list of bales for sale, what is the greatest volume of hay FJ can purchase? He cannot buy partial bales, of course; each bale is either taken whole or left behind.

Input

Line 1: Two space-separated integers, $C$ and $H$ .
Lines 2 through $H+1$ : Each line gives the volume $V_i$ of a single bale.

Output

Line 1: A single integer, the greatest total volume of hay FJ can purchase given the list of bales for sale and the capacity limit.

Examples1

Example 1
Input
```
7 3
2
6
5
```
Expected output
```
7
```