Problem Description

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.)

Input Format

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.

Output Format

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

6 15
1 5 10 20 50 100

2

3 15
1 5 11

3

Hint

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