시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 3 100.000%

문제

Farmer John is taking some of his cows to the movies! While his  truck has a limited capacity of C (100 <= C <= 5000) kilograms, he    wants to take the cows that, in aggregate, weigh as much as possible without exceeding the limit C.

Given N (1 <= N <= 16) cows and their respective weights W_i, determine    the weight of the heaviest group of cows that FJ can take to the  movies.

입력

  • Line 1: Two space-separated integers: C and N
  • Lines 2..N+1: Line i+1 contains a single integer: W_i

 

출력

  • Line 1: A single integer that is the weight of the heaviest group of cows that can go to the movies

예제 입력

259 5
81
58
42
33
61

예제 출력

242

힌트

81+58+42+61 = 242; this is the best possible sum