Coin change

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

Explanation

1. 11 → 1 + 5 + 5

2. 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: