K. 找零钱

传统题

1000ms

256MiB

当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 种面值的硬币，每种硬币有无限多个。现在需要凑出总金额 $m$ ，求最少需要多少枚硬币？如果无法凑出，输出 $-1$ 。

第一行输入两个整数 $n$ 和 $m$ ，分别表示硬币种类数和目标金额。

第二行输入 $n$ 个整数，表示每种硬币的面值。

输出一个整数，表示最少需要的硬币数量。如果无法凑出，输出 $-1$ 。

3 11
1 2 5

2 3
2 4

-1

样例 1 解释

使用 1 枚 5 元、1 枚 5 元、1 枚 1 元，共 3 枚。（或者 5+5+1 等）

对于 $100\%$ 的数据， $1 \le n \le 100$ ， $1 \le m \le 10^4$ ， $1 \le$ 硬币面值 $\le 100$ 。