Challenge: Fewest Coins (DP)

Lab Python Intermediate 20 points

Read coin values and an amount. Print the fewest coins that make exactly the amount (any coin can be used many times), or -1 if it's impossible. Greedy doesn't always work here – use DP.

Input

Line 1: coin values. Line 2: the amount (0 ≤ amount ≤ 10000).

Output

One number.

Example

Input

1 3 4
6

Output

Sample input available Sample output available

Editor

Python

Hints

best[a] = fewest coins for amount a; best[0] = 0.

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

Solution explanation

O(amount × number of coins), and it always finds the true minimum.

Show solution

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

Output

Answer