영화 보러 가기

면접 대비

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

요약

트럭 용량 C와 최대 16마리 소의 무게가 주어질 때, 합이 C를 넘지 않으면서 최대가 되는 부분집합의 무게를 구한다.

문제

농부 존이 소들을 데리고 영화를 보러 갑니다! 트럭이 실을 수 있는 최대 무게는 $C$ ( $100 \le C \le 5000$ ) 킬로그램입니다. 존은 이 한계 $C$ 를 넘지 않으면서 태운 소들의 전체 무게가 최대가 되도록 소들을 고르려고 합니다.

$N$ ( $1 \le N \le 16$ )마리의 소와 각 소의 무게 $W_i$ 가 주어질 때, 존이 트럭에 태울 수 있는 소 무리의 최대 무게를 구하세요.

첫째 줄에 두 정수 $C$ 와 $N$ 이 공백으로 구분되어 주어집니다.

이어지는 $N$ 개의 줄에는 각 줄마다 정수 $W_i$ , 즉 $i$ 번째 소의 무게가 하나씩 주어집니다.

$C$ 를 넘지 않는 소 무리의 최대 무게를 정수 하나로 출력합니다. 어떤 소도 태울 수 없다면 $0$ 을 출력합니다.