Challenge: Fewest Coins (DP)

Lab C++ Intermediate 20 points

Print the fewest coins that make the amount exactly (coins reusable), or -1.

Input

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

Output

One number.

Example

Input

3 6
1 3 4

Output

Sample input available Sample output available

Editor

C++

Hints

best[0] = 0; everything else starts at 'impossible'.

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

Solution explanation

O(amount × coins), always the true minimum.

Show solution

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

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

Output

Answer