#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

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.

Constraints

$1 \le n \le 100$
$0 \le target \le 2 \cdot 10^5$
$1 \le c_i \le 2 \cdot 10^5$

Input

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

Output

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

Samples

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

$1 \le n \le 100$
$0 \le target \le 2 \cdot 10^5$
$1 \le c_i \le 2 \cdot 10^5$

\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}