상점의 주인인 영희는 고객에게 거스름돈을 줄 때 항상 동전의 개수를 최소한으로 하여 주려고 합니다.

영희가 가지고 있는 동전은 총 N종류가 있으며, 각 동전의 가치는 임의의 양의 정수로 주어집니다.

거슬러 주어야 할 금액 K가 주어졌을 때, 영희가 최소한의 동전 개수로 거스름돈을 주기 위해 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

가지고 있는 각 종류의 동전 개수는 무한하다고 가정합니다.

입력

첫째 줄에 동전의 종류 N과 거슬러 주어야 할 금액 K가 공백을 사이에 두고 주어진다.

둘째 줄에 N개의 동전 가치 A\(i\)가 공백을 사이에 두고 오름차순으로 주어진다.

출력

첫째 줄에 금액 K를 만드는 데 필요한 동전 개수의 최솟값을 출력한다.

만약 어떤 방법으로도 정확히 금액 K를 만들 수 없는 경우에는 -1을 출력한다.

제한 사항

• 1 ≤ N ≤ 100

• 1 ≤ K ≤ 10,000

• 1 ≤ A\(i\) ≤ 10,000

Line 1: \(N\) and \(K\) (\(1 \le N \le 100\), \(1 \le K \le 10000\)). Line 2: \(N\) denominations (\(1 \le A_i \le 10000\)).

Print the minimum number of coins, or -1.

riseoj 작성

출처 Online Judge > GoldOJ