Coin Change

Lab C++ Advanced 30 points

Read coin values and an amount (≤ 10000). Print the fewest coins needed, or -1.

Input

k, the k coins, then the amount.

Output

One integer.

Example

Input

3
1 2 5
11

Output

Sample input available Sample output available

Editor

C++

Hints

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

Solution explanation

Dynamic programming solves every smaller amount once and reuses it.

Show solution

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int k, amount;
    cin >> k;
    vector<int> coins(k);
    for (int &c : coins) cin >> c;
    cin >> amount;
    vector<int> best(amount + 1, INT_MAX);
    best[0] = 0;
    for (int v = 1; v <= amount; v++) {
        for (int c : coins) {
            if (c <= v && best[v - c] != INT_MAX) best[v] = min(best[v], best[v - c] + 1);
        }
    }
    cout << (best[amount] == INT_MAX ? -1 : best[amount]) << "\n";
    return 0;
}

Output

Answer