# Coin change

π‘

The coin change problem is one of the most popular Dynamic Programming problems. It vividly demonstrates the contrast between the Greedy and Dynamic Programming approaches, and how one might find themselves falling into the trap of thinking that the greedy approach might be sufficient, while the greedy algorithm only arrives at a suboptimal result instead of solving the global problem.

Given a money system that consists of

`n`

coins, each coin has a positive value

. You are asked to find a way to obtain a total amount of `x`

by using as few coins as possible.For instance, if the coin values are

and we need to obtain `11`

, the optimal choice would be to have `1 + 5 + 5`

β 3 coins. Input

The first line of the input contains two integers

`n`

(1 β€ n β€ 100) and `x`

(1 β€ x β€ ).The next line contains

`n`

space-separated integers

(1 β€ β€ ). Output

The program should print the minimal number of coins that are necessary to get

`x`

. If it is not possible to produce the desired sum `x`

, the program should print -1. Examples

Input | Output |

3 11
1 5 7 | 3 |

3 12
1 5 7 | 2 |

Explanation

- 11 β 1 + 5 + 5

- 12 β 5 + 7

Β

Tutorial

Notice that the greedy approach of always taking the largest possible coin wonβt work. The first example demonstrates that quite nicely. If we want to get 11, and we first take the largest possible coin, it would be 7 β we need to get 11-7 = 4. Therefore, we need to get 4 1s, which will amount to 5 coins in total. While the actual answer is only 3 (5 + 5 + 1).

Letβs keep a state

`d[i]`

which will be the minimum number of coins required to obtain the sum `i`

. If weβre able to properly initialize `d`

and update all the values up to the desired sum `x`

, the final answer would be `d[x]`

itself (the minimum number of coins required to obtain `x`

).Initially, we can set all the values of

`d`

to be infinity (not possible to obtain that sum) except 0, which is possible to obtain with 0 coins:```
c = [...]
x = ...
d = [0] + [float('inf')] * x # d[0] is 0 and d[1...x] inclusive is infinity
```

Then, for each number

`1...x`

, we try to find the minimal number of coins required to get the number. If we have arrived at a number `num`

, we try all the possible coins to see if we can get `num`

by adding the value of the coin to any of the previous values obtained (`num - `

). If that improves the answer, we update `d[num]`

. So, for each `num`

in `1...x`

, we try to find all the possible previous states that could lead to `num`

and try to improve the state `d[num]`

:```
for num in range(1, x + 1): # Iterate over all the numbers 1...x inclusive
for ci in c: # Try to improve d[num] with all the coins
if num - ci >= 0: # If it's possible to obtain num with i-th coin
d[num] = min(d[num], d[num - ci] + 1)
print(d[x])
```

`d[num] = min(d[num], d[num - ci] + 1)`

is the key point in the solution of the problem. On each iteration, we try to improve the state of `d[num]`

if itβs possible to do so through `num - `

. So, we take the minimal number of coins required to obtain `num - `

and add 1 to use the coin

. When all the numbers with all the coins are processed, the final answer is just the value of

`d[x]`

.Letβs simulate the algorithm on the sample input:

`c = [1, 5, 7]`

and `x = 11`

`d = [0, β, β, β, β, β, β, β, β, β, β, β]`

`num = 1`

(try to improve the number of coins to get the sum of 1) ci = 1 β d[1] = d[0] + 1 = 1 β`d = [0, 1, β, β, β, β, β, β, β, β, β, β]`

ci = 5 β num - ci < 0 ci = 7 β num - ci < 0

`num = 2`

(try to improve the number of coins to get the sum of 2) ci = 1 β d[2] = d[1] + 1 = 2 β`d = [0, 1, 2, β, β, β, β, β, β, β, β, β]`

ci = 5 β num - ci < 0 ci = 7 β num - ci < 0

`num = 3`

(try to improve the number of coins to get the sum of 3) ci = 1 β d[3] = d[2] + 1 = 3 β`d = [0, 1, 2, 3, β, β, β, β, β, β, β, β]`

ci = 5 β num - ci < 0 ci = 7 β num - ci < 0

`num = 4`

(try to improve the number of coins to get the sum of 4) ci = 1 β d[4] = d[3] + 1 = 4 β`d = [0, 1, 2, 3, 4, β, β, β, β, β, β, β]`

ci = 5 β num - ci < 0 ci = 7 β num - ci < 0

`num = 5`

(try to improve the number of coins to get the sum of 5) ci = 1 β d[5] = d[4] + 1 = 5 β`d = [0, 1, 2, 3, 4, 5, β, β, β, β, β, β]`

ci = 5 β d[5] = d[0] + 1 = 1 β`d = [0, 1, 2, 3, 4, 1, β, β, β, β, β, β]`

ci = 7 β num - ci < 0

`num = 6`

(try to improve the number of coins to get the sum of 6) ci = 1 β d[6] = d[5] + 1 = 2 β`d = [0, 1, 2, 3, 4, 1, 2, β, β, β, β, β]`

ci = 5 β does not update ci = 7 β num - ci < 0

`num = 7`

(try to improve the number of coins to get the sum of 7) ci = 1 β d[7] = d[6] + 1 = 3 β`d = [0, 1, 2, 3, 4, 1, 2, 3, β, β, β, β]`

ci = 5 β does not update ci = 7 β d[7] = d[0] + 1 = 1 β`d = [0, 1, 2, 3, 4, 1, 2, 1, β, β, β, β]`

`num = 8`

(try to improve the number of coins to get the sum of 8) ci = 1 β d[8] = d[7] + 1 = 2 β`d = [0, 1, 2, 3, 4, 1, 2, 1, 2, β, β, β]`

ci = 5 β does not update ci = 7 β does not update

`num = 9`

(try to improve the number of coins to get the sum of 9) ci = 1 β d[9] = d[8] + 1 = 3 β`d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, β, β]`

ci = 5 β does not update ci = 7 β does not update

`num = 10`

(try to improve the number of coins to get the sum of 10) ci = 1 β d[10] = d[9] + 1 = 4 β`d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, β]`

ci = 5 β d[10] = d[5] + 1 = 2 β`d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, β]`

ci = 7 β does not update

`num = 11`

(try to improve the number of coins to get the sum of 11) ci = 1 β d[11] = d[10] + 1 = 3 β`d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3]`

ci = 5 β does not update ci = 7 β does not update

`print(d[11])`

β prints 3

Β

#### Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB