암소 베시는 다이어트를 하고 있다. 하루 칼로리양 C 를 정해 이를 초과해서 먹지 않을려고 한다. 그런데 , 농부 존은 맛있는 것이 가득 든 B 개의 바구니를 베시에게 주어 식욕을 자극하고 있다. 각 바구니에는 일정한 양의 칼로리를 가지고 있다.
당신의 일은 주어지는 C 를 초과하지 않는 상태에서 가장 이상적인 조합을 찾도록 베시를 도와 주는 것이다.
예를 들어, 한도가 40 칼로리이고 6 개의 바구니에 각각 7 , 13 , 17 , 19 ,29 , 31 의 칼로리를 가진 바구니가 주어진다면
입력 40 6 7 13 17 19 29 31 출력 39
출처: USACO December 06 Bronze