P2001 Coin Denominations

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?

The first line contains two integers: $n, m$. The next line contains $n$ integers, the coin denominations.

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

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