P2842 Banknote Problem 1.

A country has $n$ types of banknotes. Each type has denomination $a_i$, and there are infinitely many banknotes of each type. Now you need to make up an amount of $w$. What is the minimum number of banknotes needed to make up this amount? (It is guaranteed that the amount can be made up.)

The first line contains two integers $n, w$, representing the number of banknote types and the target amount to make up. The second line contains $n$ integers separated by spaces: $a_1, a_2, a_3, \dots a_n$, representing the denominations of these $n$ types of banknotes in order.

One line with one integer, representing the minimum number of banknotes used.

For $40\%$ of the testdata, $n \le 10$ and $w \le 100$. For $100\%$ of the testdata, $1 \le n \le 10^3$ and $1 \le a_i, w \le 10^4$. # Constraints Translated by ChatGPT 5