Informatica Online Judge

  eating puzzle [1780 / 06F4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 31   Total Tried : 34


The Champion of this Problem (C++) : koi17031 - 0ms / 173byte
My Best Submission (C++) : N/A

[USACO]

Background

암소 베시는 다이어트를 하고 있다.

하루 칼로리양 $C$ 를 정해 이를 초과해서 먹지 않을려고 한다.

그런데 , 농부 존은 맛있는 것이 가득 든 $B$ 개의 바구니를 베시에게 주어 식욕을 자극하고 있다. 각 바구니에는 일정한 양의 칼로리를 가지고 있다.

당신의 일은 주어지는 $C$ 를 초과하지 않는 상태에서 가장 이상적인 조합을 찾도록 베시를 도와 주는 것이다.

예를 들어, 한도가 $40$ 칼로리이고 $6$ 개의 바구니에 각각 $7$ , $13$ , $17$ , $19$ , $29$ , $31$ 의 칼로리를 가진 바구니가 주어진다면 $39$ 가 먹을 수 있는 최대 칼로리 양이다.

베시가 한도를 초과하지 않고 먹을 수 있는 최대 칼로리 양을 계산하는 프로그램을 작성하시오.

Input

첫 번째 줄은 $2$ 개의 정수 $C (10 ≤ C ≤ 35,000)$ , $B (1 ≤ B ≤ 21)$ 가 주어진다.

두번째 줄부터는 $B$ 개의 칼로리가 정수가 주어진다. 각 정수는 $1 ,2 ,3 ..$ 바구니의 칼로리이다.

Output

한도를 초과하지 않고 먹을 수 있는 최대 칼로리 양이다.

IO Example

<입력 예>
40 6
7 13 17 19 29 31

<출력예>
39

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]