纸币问题 1
题目描述
某国有 $n$ 种纸币,每种纸币面额为 $a_i$ 并且有无限张,现在要凑出 $w$ 的金额,试问最少用多少张纸币可以凑出来?
输入输出格式
输入格式
第一行两个整数 $n,w$,分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的整数 $a_1, a_2, a_3, \dots a_n$ 依次表示这 $n$ 种纸币的面额。
输出格式
一行一个整数,表示最少使用的纸币张数。
输入输出样例
输入样例 #1
6 15
1 5 10 20 50 100
输出样例 #1
2
输入样例 #2
3 15
1 5 11
输出样例 #2
3
说明
对于 $40\%$ 的数据,满足 $n\le 10$,$w\le 100$;
对于 $100\%$ 的数据,满足 $1\le n\le 10^3$,$1\le a_i \leq w\le 10^4$。