Minimum Coins - Classic Problems | Repovive

CLS52. Minimum Coins

2s256 MB

Given coin values and a target sum, find the minimum number of coins needed to form the target. Each coin value may be used any number of times.

\begin{array}{l} n \quad target \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array}

\begin{cases} \text{minimum number of coins} & \text{if possible} \\ -1 & \text{otherwise} \end{cases}

Input

3 6
1 3 4

Explanation

The target 6 is reached with 3 + 3, using two coins. No one-coin choice has value 6.

Output

Input

2 7
4 6

Explanation

Using coins of value 4 and 6 cannot make the odd target 7, so the answer is -1.

Output

-1

Input

4 0
2 5 7 11

Explanation

The target is already 0, so the empty choice uses 0 coins.

Output

\begin{array}{l} n \quad target \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array}

\begin{cases} \text{minimum number of coins} & \text{if possible} \\ -1 & \text{otherwise} \end{cases}