← 返回题目

题库练习纸币问题 1

← 上一题下一题 →

A2804 | $纸币问题 1$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

某国有 $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

3 15
1 5 11

输出 #2

C++ 编辑器

输入

输出