题目描述

给定 $n$ 种不同面值的硬币，每种硬币可以无限次使用。现在需要凑出金额 $m$，求最少需要多少枚硬币。如果无法凑出，输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10$，$1 \le m \le 1000$），分别表示硬币种类数和目标金额。

第二行包含 $n$ 个整数，表示每种硬币的面值（$1 \le$ 面值 $\le 1000$），面值之间用空格分隔。

输出格式

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

样例

输入：

3 11
1 2 5

输出：

3

数据范围

• $1 \le n \le 10$
• $1 \le m \le 1000$
• $1 \le$ 硬币面值 $\le 1000$

提示

可以使用深度优先搜索（DFS）并配合剪枝来求解。