P2842 纸币问题 1

题目描述

某国流通 n 种纸币，第 i 种纸币的面额为 (a_i)，且每种纸币都有无限张。 给定一个目标金额 w，请计算最少需要使用多少张纸币才能恰好凑出金额 (w)。 （保证一定可以凑出 (w)。

输入格式

• 第一行包含两个整数 (n, w)：纸币种数与目标金额。
• 第二行包含 (n) 个整数 (\(a_1, a_2, \dots, a_n\))：各纸币面额。

输出格式

输出一个整数，表示凑出金额 (w) 所需的最少纸币张数。

样例

样例 1

输入

6 15
1 5 10 20 50 100

输出

2

样例 2

输入

3 15
1 5 11

输出

3

说明/提示

• 数据范围：

  • 对于 (40%) 的数据：(\(n \le 10\))、(\(w \le 100\))；
  • 对于 (100%) 的数据：(\(1 \le n \le 10^3\))、(\(1 \le a_i, w \le 10^4\))。
• 每种面额可使用任意张（包含 0 张）。
• 不要求输出具体选取方案，仅输出最少张数。