Minimum Coins for Consecutive Sums

You are about to go shopping and want to carry as few coins as possible. You originally have N different coin types with infinite supply, with each coin type having a unique denomination. You want to select a set of coins (possibly choosing multiple coins of the same type) so that you can form every integer value from 1 to X (each coin can be used at most once in forming a sum). Your task is to determine the minimum number of coins you must carry in order to achieve this.

Note: It is guaranteed that the available coin denominations allow you to form every value in the range [1, X].

Mathematical Formulation:

Let the current achievable sum be cur, initially 0. At each step, you may add a coin of denomination d (with d chosen from the available types) provided that d ≤ cur + 1 in order to extend the achievable range to cur + d. Continue this process until cur ≥ X. The objective is to minimize the number of coins used.

This problem can be solved using a greedy strategy where, at every step, you choose the coin with the largest denomination that is ≤ cur + 1.

inputFormat

The input consists of two lines. The first line contains two integers N and X, where 1 ≤ N ≤ 10^5 and 1 ≤ X ≤ 10^9. The second line contains N space-separated integers representing the coin denominations. It is guaranteed that at least one coin has denomination 1.

outputFormat

Output a single integer: the minimum number of coins that must be carried so that every integer value in the range [1, X] can be formed using a subset of the carried coins (each coin can be used at most once). If it is impossible, output -1.

sample

3 6
1 3 4

4