준규가 가진 동전은 \(N\)가지이고 각 종류를 매우 많이 가지고 있다. 동전의 가치 \(A_1 < A_2 < \dots < A_N\)에는 특별한 성질이 있다: \(A_1 = 1\)이고, 각 동전의 가치는 그 다음 동전 가치의 약수이다 (즉 \(A_{i+1}\)은 \(A_i\)의 배수).

동전을 적절히 사용해 합을 정확히 \(K\)로 만들 때, 필요한 동전 개수의 최솟값을 구하여라.

\(1 \le N \le 10\), \(1 \le K \le 100\,000\,000\), \(A_1 = 1\), \(A_i\)는 \(A_{i+1}\)의 약수.

첫째 줄에 \(N\)과 \(K\)가 주어진다. 둘째 줄부터 \(N\)개의 줄에 동전의 가치가 오름차순으로 주어진다.

합을 \(K\)로 만드는 데 필요한 동전 개수의 최솟값을 출력한다.

riseoj 작성

출처 Original