题目描述

给定不同面额的硬币和一个总金额。计算可以凑成总金额所需的硬币个数最少的数量。如果没有任何一种硬币组合能组成总金额，返回 $-1$。

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

输入格式

第一行两个整数 $n$ 和 $amount$，分别表示硬币种类数和总金额。

第二行 $n$ 个整数，表示每种硬币的面额。

输出格式

输出一个整数，表示最少硬币数量。如果无法凑成，输出 $-1$。

输入输出样例 #1

输入 #1

样例

输入

3 11

输出

1 2 5

输出 #1

3

说明/提示

数据范围

• $1 \le n \le 12$
• $1 \le amount \le 10^4$
• $1 \le$ 硬币面额 $\le 10000$