Minimum Coins to Cover All Prices

Given n types of coins with given denominations (each coin type is available in an unlimited supply) and a maximum price m, find the minimum number of coins that one must carry such that for every price from 1 to m (inclusive) there exists a subset of the carried coins whose sum equals that price exactly. Note that each coin can be used at most once in each representation. The coins may be repeated in the selection. All coin denominations are positive integers.

Mathematical Formulation:

Let the coins chosen be \( c_1, c_2, \ldots, c_k \) (not necessarily distinct) and let \( S = c_1 + c_2 + \cdots + c_k \). We require that by selecting a subset of these coins, every integer value \( x \) with \( 1 \le x \le m \) can be represented as the sum of some of the \( c_i \)'s. A necessary and sufficient condition for this (when coins are taken in non-decreasing order \( c_1 \le c_2 \le \cdots \le c_k \)) is that \( c_1 = 1 \) and for every \( i \ge 2, c_i \le c_1+c_2+\cdots+c_{i-1}+1 \).

If it is impossible to cover all prices from 1 to m using the available coin types, output -1.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹), representing the number of coin types and the maximum price respectively.

The second line contains n space-separated positive integers representing the values of the coins.

It is guaranteed that the coin values are given in arbitrary order.

outputFormat

Output a single integer representing the minimum number of coins needed to be carried to cover every price from 1 to m. If it is impossible, print -1.

sample

2 6
1 3

4