거스름돈 만들기

가엾은 소 베시(Bessie)가 국경 너머 슬로보비아(Slobbovia)에 있는 편의점에서 일하게 되었습니다. 슬로보비아는 미국과 다른 화폐 체계를 쓰는데, 동전의 액면가가 날마다 바뀝니다!

베시가 손님에게 거스름돈을 최적으로, 즉 동전 개수를 가장 적게 거슬러 줄 수 있도록 도와주세요. 거슬러 줄 금액은 $C$센트($1 \le C \le 1000$)이고, 쓸 수 있는 동전의 종류는 $N$가지($1 \le N \le 10$)입니다. 같은 종류의 동전은 개수 제한 없이 얼마든지 쓸 수 있으며, 모든 입력은 주어진 동전들로 항상 정확히 거슬러 줄 수 있습니다.

예를 들어 액면가가 50, 25, 10, 5, 1인 다섯 종류의 동전을 쓸 수 있다면, 93센트는 50 한 개, 25 한 개, 10 한 개, 5 한 개, 1 세 개, 즉 모두 7개의 동전으로 최소 개수로 거슬러 줄 수 있습니다.

• 첫째 줄: 두 정수 $C$와 $N$이 공백으로 구분되어 주어진다.
• 둘째 줄부터 $N+1$번째 줄까지: 각 줄에 쓸 수 있는 동전의 액면가가 하나씩 주어진다. 모든 액면가는 서로 다른 정수이다.

• 첫째 줄: $C$센트를 만드는 데 필요한 동전의 최소 개수를 정수 하나로 출력한다.