Coin Change (DP)

Lab Python Advanced 30 points

Read coin values and an amount. Print the minimum number of coins needed to make the amount, or -1 if impossible.

Input

Line 1: coin values. Line 2: amount.

Output

One integer.

Example

Input

1 2 5
11

Output

Sample input available Sample output available

Editor

Python

Hints

best[v] = fewest coins for value v.

best[v] = min over coins c of best[v - c] + 1.

Solution explanation

Dynamic programming builds the answer for every smaller amount first and reuses it.

Show solution

coins = list(map(int, input().split()))
amount = int(input())
INF = float("inf")
best = [0] + [INF] * amount
for value in range(1, amount + 1):
    for c in coins:
        if c <= value and best[value - c] + 1 < best[value]:
            best[value] = best[value - c] + 1
print(best[amount] if best[amount] != INF else -1)

Output

Answer