KOI국의 화폐 체계에는 1원짜리 동전을 포함하는 N개의 동전이 있다.

홍윤이는 KOI국에서 여행을 온 관광객이다.

홍윤이는 동전을 모으는 취미가 있어서 여행을 온 김에 KOI 국의 동전들을 종류별로 수집하기로 했다.

여행은 끝이 나고 이제 홍윤이는 공항 앞에서 마지막 쇼핑을 하기로 했다.

지금 홍윤이의 지갑에는 K원짜리 지폐 한 장이 들려있고 가게에는 1 \thicksim K-1원까지의 모든 물건이 있다.

(KOI국의 N종류의 동전 모두 K원보다 가치가 작다.)

홍윤이는 이미 몇 개의 동전을 모았고, 딱 하나의 물건을 사서 최대한 많은 종류의 동전을 집으로 가져가려 한다.

가게에서 물건을 사면 가게 주인은 다음과 같이 거스름돈을 줄 것이다.

1. 남은 거스름돈보다 작거나 같은 동전 중 가장 액수가 큰 동전을 지불한다.

2. 지불한 액수만큼 남은 거스름돈을 차감하고, 잔액이 0이 될 때까지 반복한다.

가령 1, 3, 7, 11원의 동전이 있고 홍윤이가 30원 지폐를 내서 15원짜리 물건을 구매했다고 하자.

이때 가게 주인은 15원의 거스름 돈을 11원, 3원, 1원의 동전으로 차례대로 지불한다.

N개의 동전과 K, 홍윤이가 이미 모은 동전들의 정보가 주어질 때 홍윤이가 최대한 동전을 많이 모으는 방법을 구해보자.

동전 수집가 timer 1s memory 128MB

동전 수집가 1s 128MB