10078 동전 교환 Silver II

문제

N가지 종류의 동전이 있다. 각 동전의 가치가 주어질 때, 합이 K원이 되는 최소 동전 수를 구하는 프로그램을 작성하시오. 각 동전은 무한히 사용할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 K (1 ≤ K ≤ 10,000)가 주어진다. 둘째 줄에 N개의 동전 가치가 주어진다. (1 ≤ 가치 ≤ 10,000)

출력

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

3 15
1 5 12

3