Description

Xiao A has $n$ types of coins and wants to buy an item priced at no more than $m$ yuan. He does not want to receive change (it’s dirty), and he also does not want to carry too many coins. Each denomination can be used repeatedly. Given the denominations of these $n$ types of coins, what is the minimum number of coins needed so that all prices from $1$ to $m$ can be formed exactly?

Input Format

The first line contains two integers: $n, m$.

The next line contains $n$ integers, the coin denominations.

Output Format

Output a single integer: the minimum number of coins. If there is no solution, output No answer!!!.

5 31
1 2 8 4 16

5

Hint

Constraints

Only testcases 9 and 10 are designed to trip people; greedy is fine.

For $20\%$ of the testdata, $1 \le n \le 10$, $1 \le m \le 100$.
For $60\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10000$.
For $80\%$ of the testdata, $1 \le n \le 30000$, $1 \le m \le 2 \times 10^9$.
For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $1 \le m \le 2^{63}$.

Translated by ChatGPT 5