# your code goes here
import copy
CONST_INFINITY = 1000000
def bank(cash, coins):
    ways = {0: 0}
    for start_sum in range(1, cash + 1):
        ways[start_sum] = CONST_INFINITY
        variable_coins = copy.copy(coins)
        coins_nom = variable_coins.keys()
        coins_nom.sort()
        for coins_value in coins_nom:
            if variable_coins[coins_value] != 0 and start_sum >= coins_value and ways[start_sum - coins_value] + 1 < ways[start_sum]:
                ways[start_sum] = ways[start_sum - coins_value] + 1
                variable_coins[coins_value] -= 1
    return ways[cash]
print bank(16, {1: 3, 2: 7, 7: 4, 10: 1})