SPOJ.com - Problem EATPUZZ

EATPUZZ - Eating Puzzle

no tags

Bessie is on a diet where she can eat no more than C (10 ≤ C ≤ 35,000) calories per day. Farmer John is teasing her by putting out B (1 ≤ B ≤ 21) buckets of feed, each with some (potentially non-unique) number of calories (range: 1..35,000). Bessie has no self-control: once she starts on a feed bucket, she consumes all of it.

Bessie is not so good at combinatorics. Determine the optimal combination of feed buckets that gives Bessie as many calories without exceeding the limit C.

As an example, consider a limit of 40 calories and 6 buckets with 7, 13, 17, 19, 29, and 31 calories. Bessie could eat 7 + 31 = 38 calories but could eat even more by consuming three buckets: 7 + 13 + 19 = 39 calories. She can find no better combination.

Input

For each test case, there are two integers: C and B.

B space-separated integers that respectively name the number of calories in bucket 1, 2, etc.

Output

A single line with a single integer that is largest number of calories Bessie can consume and still stay on her diet.

Example

Input:
40 6
7 13 17 19 29 31
100 4
90 4 2 6

Output:
39
100

Submit solution!

hide comments



	nadstratosfer: 2018-06-23 06:48:28 Wasted 20mins because of stupid input format. There are multiple testcases although statement implies otherwise ("Output a single line...") but they are NOT separated with a blankline as in the example. As for the tutorial-or-not discussion, SPOJ badly needs better hierarchy, both for points and visibility. The way it is now, the tutorial category is effectively a forgotten dump. It features every trash of a problem; whenever there's a question set poorly, trivial to solve, worded unintelligibly or a carbon copy of another one - it gets moved to tutorial. Where's tutoring in that? At the same time there's way too many interesting, original problems here that offer fun and opportunity to learn, but they were demoted because, the horror, bruteforce in C would get you AC. So now nobody knows about them since it's a competitive programming website and without scoring there is no competition. SPOJ needs an "easy" section with scoring where perhaps ~20% of current tutorial problems and some from basics belong, and "misc" for the rest. That being said, this one belongs here just fine as there are several similar problems in classical.
	Noszály Csaba: 2013-03-15 21:11:41 Francky : There are more harder problems in the tutorial section and there are easier problems in classical. The scoring formula should be altered in a way that easy problems get points close to zero: 100/(100+x+a(x/b)^c) with a,b,c=1,100,4 for example.So the problem will tutorify itself. --ans--> It's not only for points, but also for visibility. Classical section should contain mostly not so easy and interesting problems, if you set a new formula and merge all problems, the good ones will be less visible. I agree that's not an easy task. Some problems with many AC are very good, some with very few also, and the contrary. Not easy. Last edit: 2013-03-15 21:27:48
	Francky: 2013-03-14 17:17:38 The hardest part of the problem is to read that is written in small in "Output" request. This problem is tutorial, it should be moved. Another comment in that way ?
	Rahul Shah: 2013-03-14 15:56:49 excellent sum for beginners...:D HINT:(knapsack)
	Tushar Makkar (Retired): 2013-03-14 09:56:41 Thank you for making the problem more clearer Last edit: 2013-03-14 10:55:02

Submit solution!

Added by:	[UNI]Jonathans
Date:	2013-03-14
Time limit:	1.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	USACO 2006