bankomati

In the new era of electronic wonders, automated teller machines (ATMs) are becoming a common thing. Banks want their clients to remain at the ATMs for as short a time as possible so that more people could use them. For this reason they want to give money to their clients in as few bills as possible. However, ATMs were set up by lazy programmers who used the simplest algorithm. Each time the ATMs first give the largest bill not larger than the complete sum to be given and then they give the remaining amount in smaller bills. For example, in a system with bills of 1, 7 and 10 dollars the sum of 14 dollars will be paid off with 1 bill of 10 and 4 bills of 1 dollar, which gives 5 bills altogether. This is not in compliance with the bank’s policy, because 14 dollars could be paid off with only 2 bills of 7 dollars.

Your task is to write a program which will, for a given system of bills (which always contains a 1 dollar bill), find the smallest amount that can be paid off with fewer bills than the ATM would give.