영화 보러 가기

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

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

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

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

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