零钱兑换

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

输入格式

第一行包含两个整数 $n$ 和 $amount$，分别表示硬币种类的数量和需要凑成的总金额。 第二行包含 $n$ 个整数，表示不同面额的硬币数组 $coins$。

输出格式

输出一个整数，表示凑成总金额所需的最少的硬币个数。如果无法凑成，请输出 -1。

样例

样例输入 1

3 11
1 2 5

样例输出 1

3

样例解释： $11 = 5 + 5 + 1$。

样例输入 2

1 3
2

样例输出 2

-1

样例输入 3

1 0
1

样例输出 3

0

数据范围与提示

• $$1 \le n \le 12$$
• $$1 \le coins[i] \le 2^{31} - 1$$
• $$0 \le amount \le 10^4$$