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

문제

최백준 조교는 사실 엄청난 갑부다. 그는 그 사실을 숨겼지만 어느 날 김재홍 조교에게 그 사실을 발각 당한다. 결국 최백준 조교는 가지고 있는 돈을 몽땅 동전으로 바꾸어서 땅에 묻어 둘 생각을 하게 된다.

하지만 최백준 조교가 가진 돈이 워낙 많기 때문에 돈을 묻어두어도 그 위치가 김재홍 조교에게 발각될 위험이 있다.

그 때문에 그는 최소의 동전 개수로 돈을 바꾸고 싶다.

최백준 조교는 엄청난 구두쇠이기 때문에 돈이 단 1원도 줄거나, 심지어는 늘어나는 것도 싫어한다.

정확히 그가 가진 금액을 동전으로 교환하되, 그 개수를
...........최소화 하는 방법을 찾도록 하자.

입력

첫째 줄에는 엄청난 갑부인 최백준 조교가 가진 돈의 금액(10^9 <= M <= 10^18)이 주어진다. 두 번째 줄에는 동전의 종류 N(1 <= N <= 1,000)와 세 번째 줄에는  Ai, 즉, i번째 동전의 금액이 주어진다. (1 <= Ai <= 10,000)
 1원짜리 동전은 항상 있기 때문에, 금액을 못 만드는 경우는 항상 없다.

출력

동전으로 딱 맞는 금액을 만들 때, 그 개수를 출력한다.

예제 입력

1000000001
2
10000 1

예제 출력

100001

힌트

출처

  • 문제를 만든 사람: xhark