Problem 41: Coin Change Problem

Problem Statement: Given a list of coin denominations and a target sum, compute the minimum number of coins required to make up that sum. If it is not possible, output -1.

Input

The first line contains two integers n and target, where n is the number of coin denominations. The second line contains n space-separated integers representing the coin values.

Output

Print the minimum number of coins required to obtain the target sum, or -1 if not possible.

Examples


Input:
3 11
1 2 5

Output:
3

Solution in C++


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

const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, target; cin >> n >> target;
    vector<int> coins(n);
    for(int i = 0; i < n; i++) cin >> coins[i];
    
    vector<int> dp(target + 1, INF);
    dp[0] = 0;
    
    for(int i = 1; i <= target; i++){
        for(int coin : coins){
            if(i - coin >= 0)
                dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
    
    cout << (dp[target] == INF ? -1 : dp[target]) << "\n";
    return 0;
}