먹이 퍼즐

면접 대비

시간 제한1초메모리 제한128 MB

요약

최대 21개의 통 크기와 칼로리 한도가 주어질 때, 한도를 넘지 않으면서 합이 가장 큰 부분집합을 고른다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 비트 연산, 배열, 재귀
정답자: 아직 제출이 없습니다

문제

베시(Bessie)는 하루에 $C$ ( $10 \le C \le 35000$ )칼로리를 넘지 않게 먹어야 하는 다이어트 중이다. 농부 존은 베시를 놀리려고 여물통 $B$ 개( $1 \le B \le 21$ )를 내놓았고, 각 통에는 어떤 양의 칼로리가 담겨 있다(값의 범위는 $1$ 부터 $35000$ 까지이며, 서로 같을 수도 있다). 베시는 자제력이 없어서 한 통을 먹기 시작하면 그 통을 전부 비운다.

베시는 조합 계산에 약하다. 제한 $C$ 를 넘지 않으면서 베시가 최대한 많은 칼로리를 먹을 수 있도록 여물통을 골라, 그때 먹게 되는 칼로리의 최댓값을 구하라.

입력

1번째 줄: 공백으로 구분된 두 정수 $C$ 와 $B$
2번째 줄: 공백으로 구분된 $B$ 개의 정수. 각각 1번, 2번, ... 여물통에 담긴 칼로리를 나타낸다.

출력

1번째 줄: 베시가 다이어트를 지키면서 먹을 수 있는 칼로리의 최댓값을 나타내는 정수 하나.

예제1

예제 1
입력
```
40 6
7 13 17 19 29 31
```
예상 출력
```
39
```