题目描述

有 $n$ 种面值不同的硬币，每种硬币都可以使用任意多枚。给定目标金额 $m$，请计算凑出金额 $m$ 至少需要多少枚硬币。如果无法凑出，输出 -1。

输入格式

第一行输入两个整数 $n$、$m$。

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

输出格式

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

输入输出样例

输入

3 11
1 2 5

输出

3

数据范围与提示

对于全部数据，$1 \le n \le 100$，$1 \le m \le 10000$，硬币面值不超过 $10000$。

可以令 $dp[i]$ 表示凑出金额 $i$ 所需的最少硬币数。初始时 $dp[0]=0$，其他位置设为一个很大的数。枚举每种硬币面值 $c$，用 $dp[i-c]+1$ 更新 $dp[i]$。

来源

GESP 6 级动态规划训练。