동전 교환

문제 설명

서로 다른 금액의 동전 배열 coins와 총 금액 amount가 주어집니다.

해당 금액을 만드는 데 필요한 최소 동전 개수를 반환하세요. 불가능하면 -1을 반환합니다.

입력 형식

첫째 줄에 동전 종류의 수 N과 목표 금액 amount가 주어집니다.

둘째 줄에 N개의 동전 금액이 공백으로 구분되어 주어집니다.

출력 형식

최소 동전 개수를 출력합니다. 불가능하면 -1을 출력합니다.

제약 조건

• 1 ≤ N ≤ 12
• 1 ≤ coins[i] ≤ 2^31 - 1
• 0 ≤ amount ≤ 10^4