CSES: Minimizing Coins

 Minimizing Coins

Consider a money system consisting of n$n$ coins. Each coin has a positive integer value. Your task is to produce a sum of money x$x$ using the available coins in such a way that the number of coins is minimal.

For example, if the coins are {1,5,7}$\{1,5,7\}$ and the desired sum is 11$11$, an optimal solution is 5+5+1$5+5+1$ which requires 3$3$ coins.

Input

The first input line has two integers n$n$ and x$x$: the number of coins and the desired sum of money.

The second line has n$n$ distinct integers c1,c2,…,cn$c_1,c_2,\dots ,c_n$: the value of each coin.

Output

Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print −1$-1$.

Constraints

• 1≤n≤100$1\le n\le 100$
  
• 1≤x≤106$1\le x\le {10}^6$
  
• 1≤ci≤106$1\le c_i\le {10}^6$
  

Example

Input:
3 11
1 5 7

Output:
3




	#include <bits/stdc++.h>
	using namespace std;
	int main() {
	int n, target;
	cin >> n >> target;
	vector<int> c(n);
	for (int& v : c) cin >> v;
	vector<int> dp(target + 1, 1e9);
	dp[0] = 0;
	for (int i = 1; i <= target; i++) {
	for (int j = 0; j < n; j++) {
	if (i - c[j] >= 0) {
	dp[i] = min(dp[i], dp[i - c[j]] + 1);
	}
	}
	}
	cout << (dp[target] == 1e9 ? -1 : dp[target]) << endl;
	}

view raw Minimizing Coins.cpp hosted with ❤ by GitHub