"두 번째 줄에는 동전의 종류 N와 세 번째 줄에는 Ai, 즉, i번째 동전의 금액이 주어진다."라는 '문장'은 교체되기 충분합니다.

추가로, 문제 지문에도 오타가 있습니다.

"발각 당한다" -> 발각당한다

"최소화 하는" -> 최소화하는

입력

첫째 줄에는 엄청난 갑부인 최백준 조교가 가진 돈의 금액(10⁹ ≤ M ≤ 10¹⁸)이 주어진다. 두 번째 줄에는 동전의 종류 N(1 ≤ N ≤ 1,000)이 주어진다. 세 번째 줄에는 동전의 금액 A_i (1 ≤ A_i ≤ 10,000)가 N개 주어진다.

N가지의 동전 중 1원짜리 동전은 항상 있기 때문에, 금액을 못 만드는 경우는 없다.

출력

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