零钱兑换（Coin Change）

**题目难度：**中等

题目描述

给定 (n) 种不同面额的硬币，以及一个整数 amount，表示需要凑出的金额。

每种面额的硬币都有无限枚。请计算凑出 amount 所需的最少硬币数量。

如果无法凑出该金额，输出 -1。

输入格式

第一行包含两个整数 (n) 和 amount，分别表示硬币面额的种类数和需要凑出的金额。

第二行包含 (n) 个整数，表示每种硬币的面额。

输出格式

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

数据范围

• (1 \le n \le 12)
• (1 \le \text{硬币面额} \le 2^{31}-1)
• (0 \le \text{amount} \le 10^4)

样例 1

输入

3 11
1 2 5

输出

3

说明

最少需要 3 枚硬币：(11=5+5+1)。

样例 2

输入

1 3
2

输出

-1

说明

只有面额为 2 的硬币，无法凑出金额 3。

样例 3

输入

1 0
1

输出

0