문제
농부 창호는 자신이 기르는 소들을 데리고 영화를 보러 가고자 한다.
영화관이 꽤나 먼 거리에 위치 해 있기 때문에 자신의 트럭을 몰고 가야 한다.
허나 트럭은 적재 할 수 있는 무게의 한계가 있기 때문에, 소들 중에서 몇 마리를 골라서 영화를 보여주고자 한다.
가급적이면 무게의 한계를 넘어서지 않으며 최대한 많은 무게의 소들을 데리고 가려고 한다.
다시 말해서, 태우게 되는 소들의 무게의 합이 최대가 되게 한다는 것이다. 이를 위한 프로그램을 작성하라.
입력
첫 번째 줄에는 트럭의 용량 한계 C(100≤C≤5000)와 창호가 기르는 소의 마리수 N(1≤N≤16)이 입력된다. 그 다음 줄 부터는 N개의 기르고 있는 소들의 무게가 입력된다.
출력
한줄에 C를 넘지 않게 소들을 실었을 때의 최대 무게의 합을 출력한다.
예제
259 5
81
58
42
33
61
242
출처
USACO US Open 2008 Bronze 2번
로그인해야 코드를 작성할 수 있어요.