여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의 개발을 의뢰받았다.
이번에도 역시 자동판매기에서 이용자에게 거스름돈을 남겨줄 때, 거스름돈에 사용될 동전의 수를 가정 적게하는 것이다.
입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가지 수 그리고 동전의 종류가 들어온다.
여러분은 그 돈의 액수를 거슬러 주는 여러가지 방법들 중 가장 적은 동전은 몇개인지 구하는 프로그램을 작성해야 된다.

첫 번째 줄에 거슬러 줄 돈의 액수가 입력된다. (이 값은 최대 1000000원을 넘지 않는다.)
두 번째 줄에 그 나라에서 사용되는 동전의 가지 수가 입력된다. (최대 20개)
마지막 줄에는 동전의 종류별 액수가 입력된다. (동전의 최대값은 10000원, 입력되는 동전은 정렬되어 있지 않다.)

지불할 최소의 동전의 개수를 출력한다.

100원 3개 10원 2개 고로 답은 5 이 이하의 경우는 없다.

koistudy.net