题目描述

现有 $n$ 种纸币，第 $i$ 种的面额是 $a_i$，每种均可使用任意多张。请恰好凑出金额 $w$，并求所需纸币张数的最小值。数据保证存在可行方案。

输入格式

第一行给出两个正整数 $n$ 和 $w$，分别表示面额种数与目标金额。

第二行给出 $n$ 个正整数 $a_i$，表示各个面额。

输出格式

输出恰好凑出目标金额所需的最少纸币张数。

6 15
1 5 10 20 50 100

2

3 15
1 5 11

3

数据范围

• $40\%$ 的数据：$n\le 10$，$w\le 100$。
• 全部数据：$1\le n\le 10^3$，$1\le a_i,w\le 10^4$。