예산집행 - 구름LEVEL
예산집행
Quiz Info
Quiz Info
예산집행
100points
Participant
30
Solved Rate
83.3%
2
0

구름시 시장인 구름이는 예산 범위를 넘지 않는 선에서 다양한 활동을 하고 싶어 합니다.

예를 들어 지금 남은 예산(B)이 40이고(단위:억), 예산을 사용할 수 있는 활동(n)이 6개가 있습니다. 6개의 활동에 각각 드는 비용은 7, 13, 17, 19, 29, 31(단위:억)입니다. 여기서 40을 채울 수 있는 활동의 개수는 상관이 없습니다. 40을 넘지 않는 범위에서 활동 비용을 조합해보면 다음과 같습니다.

  • 7 + 13 + 17 = 37
  • 7 + 31 = 38
  • 7 + 13 + 19 = 39

따라서 40을 초과하지 않으면서 예산을 최대로 사용할 수 있는 비용은 39입니다.

구름시장 구름이를 도와 예산을 최대로 사용할 수 있는 비용을 구하는 프로그램을 작성하십시오.


입력

첫째 줄에 남은 예산(B) 입력 ( 10 ≤ B ≤ 35,000 인 정수 )

둘째 줄에 예산을 사용할 수 있는 활동의 수(n) 입력 (1 ≤ n ≤ 21 )

셋째 줄에 공백으로 구분하여 n개의 활동비 입력 (양의 정수)

출력

남은 예산을 초과하지 않으면서 최대로 사용할 수 있는 비용 출력

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
40
6
71317192931
Output
39
Example 2
Input
35
3
111314
Output
27
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)