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

영희가 가지고 있는 동전은 총 N종류가 있다.

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

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

입력

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

둘째 줄부터 N개의 줄에 걸쳐 동전의 가치 A\(i\)가 오름차순으로 한 줄에 하나씩 주어진다. (A\(1\)은 항상 1이며, A\(i\)는 A\(i-1\)의 배수이다.)

출력

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

제한 사항

• 1 ≤ N ≤ 12

• 1 ≤ K ≤ 100,000,000

• 1 ≤ A\(i\) ≤ 50,000,000 (A\(1\) = 1, i ≥ 2일 때 A\(i\)는 A\(i-1\)의 배수)

Line 1: \(N\) and \(K\) (\(1 \le N \le 12\), \(1 \le K \le 10^8\)). Next \(N\) lines: the denominations, one per line.

Print the minimum number of coins.

riseoj 작성

출처 Online Judge > GoldOJ