문제
은행원인 동수는 지폐를 동전으로 교환하는 손님들의 편의를 위해 최소 동전수로 교환해 주려고 한다. 즉, 500원, 100원, 10원 동전 단위가 사용될 때 1,000원에 대한 최소 동전수는 500원 2개, 즉 2다. N개의 동전 단위와 거스름돈 W가 주어질 때, 주어진 거스름돈을 거슬러 주는 최소 동전 수를 구하는 프로그램을 작성하시오. 단, 각 동전 단위의 개수는 무한대다. 예를 들어, 4개의 동전 단위 50원, 12원, 5원, 1원이 주어질 때 거스름돈 15원의 최소 동전 수는 3이다. 즉, 5원 3개가 거스름돈 15원의 가장 작은 동전 수다. |
입력
첫째 줄에 동전 단위의 개수 N(1<=N<=1000)이 주어진다. 두 번째 줄에 N개의 동전 단위가 공백을 사이에 두고 오름차순으로 주어진다. 각 동전의 금액은 10,000 이하다. 세 번재 줄에 거스름돈 W(1<=W<=1000000)가 주어진다.
출력
첫째 줄부터 최소 동전수를 출력한다.
예시 1
입력
4
1 5 12 50
15
출력
3
예시 2
입력
6
1 5 10 25 50 100
138
출력
6