题目描述

《零钱兑换（一）》

给定 n 种硬币，第 i 种硬币的面值为 coins[i] ，目标金额为 m。假设每一种面额的硬币有无限个。问能够凑出目标金额的最少硬币数量。

输入格式

输入的第一行是两个正整数 n 和 m，用空格隔开，其中1≤n ≤20,表示正整数的个数，m为目标金额(1≤m ≤1000); 接下来的一行是n个正整数，用空格隔开。

输出格式

输出凑出目标金额的最少硬币数量。如果无法凑出目标金额，则输出 -1 。

样例

输入样例 1

4 23
1 2 5 10

输出样例 1

4

输入样例 2

1 3
2

输出样例 2

-1

输入样例 3

1 10
5

输出样例 3

2

输入样例 4

3 7
3 5 1

输出样例 4

3