# 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})

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmltcG9ydCBjb3B5CkNPTlNUX0lORklOSVRZID0gMTAwMDAwMApkZWYgYmFuayhjYXNoLCBjb2lucyk6CiAgICB3YXlzID0gezA6IDB9CiAgICBmb3Igc3RhcnRfc3VtIGluIHJhbmdlKDEsIGNhc2ggKyAxKToKICAgICAgICB3YXlzW3N0YXJ0X3N1bV0gPSBDT05TVF9JTkZJTklUWQogICAgICAgIHZhcmlhYmxlX2NvaW5zID0gY29weS5jb3B5KGNvaW5zKQogICAgICAgIGNvaW5zX25vbSA9IHZhcmlhYmxlX2NvaW5zLmtleXMoKQogICAgICAgIGNvaW5zX25vbS5zb3J0KCkKICAgICAgICBmb3IgY29pbnNfdmFsdWUgaW4gY29pbnNfbm9tOgogICAgICAgICAgICBpZiB2YXJpYWJsZV9jb2luc1tjb2luc192YWx1ZV0gIT0gMCBhbmQgc3RhcnRfc3VtID49IGNvaW5zX3ZhbHVlIGFuZCB3YXlzW3N0YXJ0X3N1bSAtIGNvaW5zX3ZhbHVlXSArIDEgPCB3YXlzW3N0YXJ0X3N1bV06CiAgICAgICAgICAgICAgICB3YXlzW3N0YXJ0X3N1bV0gPSB3YXlzW3N0YXJ0X3N1bSAtIGNvaW5zX3ZhbHVlXSArIDEKICAgICAgICAgICAgICAgIHZhcmlhYmxlX2NvaW5zW2NvaW5zX3ZhbHVlXSAtPSAxCiAgICByZXR1cm4gd2F5c1tjYXNoXQpwcmludCBiYW5rKDE2LCB7MTogMywgMjogNywgNzogNCwgMTA6IDF9KQ==