무인 매점의 키오스크가 손님에게 거스름돈을 내어 줄 때, 사용하는 동전의 개수를 최소로 하려고 한다.

키오스크가 보유한 동전의 액면(금액)은 큰 것부터 작은 것 순서로 주어지며, 각 액면은 바로 다음(한 단계 작은) 액면의 배수이다. 즉 액면들이 서로 배수 관계로 겹겹이 포함되어 있다. 각 액면의 동전은 필요한 만큼 얼마든지 쓸 수 있으며, 거스름돈 \(M\) 은 항상 가장 작은 액면의 배수이므로 정확히 거슬러 줄 수 있다.

거스름돈 \(M\) 원을 정확히 만들기 위해 필요한 동전의 최소 개수를 구하여라.

예를 들어 액면이 \(500, 100, 50, 10\) 이고 거스름돈이 \(1260\) 원이라면, \(500\) 원 두 개, \(100\) 원 두 개, \(50\) 원 한 개, \(10\) 원 한 개로 모두 \(6\) 개의 동전이 필요하다.

\(0 \le M \le 10^9\)

\(1 \le K \le 30\)

액면은 큰 것부터 작은 것 순서이며, 각 액면은 다음 액면의 배수이다. 모든 액면은 \(1\) 이상 \(10^9\) 이하이고, \(M\) 은 가장 작은 액면의 배수이다.

첫째 줄에 거스름돈 \(M\) 과 동전 액면의 개수 \(K\) 가 공백을 사이에 두고 주어진다. (\(0 \le M \le 10^9\), \(1 \le K \le 30\))

둘째 줄에 \(K\) 개의 액면이 큰 것부터 작은 것 순서로 공백으로 구분되어 주어진다. 각 액면은 바로 다음 액면의 배수이다. 모든 액면은 \(1\) 이상 \(10^9\) 이하의 서로 다른 정수이며, \(M\) 은 항상 가장 작은 액면의 배수이다.

거스름돈 \(M\) 을 정확히 만들기 위해 필요한 동전의 최소 개수를 출력한다.

riseoj 작성

출처 Original