엄청난 부자의 동전 교환

한 사람이 매우 많은 돈을 가지고 있다. 그는 이 금액을 모두 동전으로 바꾸어 보관하려고 한다.

동전의 개수가 많을수록 보관하기 어렵기 때문에, 주어진 동전 종류를 사용해 정확히 같은 금액을 만들면서 동전 개수를 최소화하고 싶다. 금액이 1원이라도 줄거나 늘어나서는 안 된다.

정확히 M원을 동전으로 만들 때 필요한 동전의 최소 개수를 구하라.

첫째 줄에 금액 M이 주어진다. (10^9 <= M <= 10^18)

둘째 줄에 동전 종류의 수 N이 주어진다. (1 <= N <= 1,000)

셋째 줄에 각 동전의 금액 A_i가 N개 주어진다. (1 <= A_i <= 10,000)

동전 종류에는 1원짜리 동전이 항상 포함되므로, 어떤 금액도 만들 수 있다.

정확히 M원을 만들기 위해 필요한 동전의 최소 개수를 출력한다.