동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣입력설명 첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종 류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

import sys
sys.stdin=open("input.txt","rt")
# n,m = map(int,input().split())
# n = int(input())
# arr = list(map(int,input().split()))

def DFS(i,sum):
    global res
    if i >res:
        return
    if sum > m:
        return
    if sum == m :
        if res > i:
            res = i
    
    else:
        for j in range(n):
            DFS(i + 1,sum+a[j])
        
        


if __name__ =="__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())),reverse=True)
    m = int(input())
    res = 21470000
    DFS(0,0)
    print(res)