晶石拼凑

题目描述

在古老的魔法仪式中，祭司需要让能量法阵的总法力值恰好达到 $M$。

法阵可以通过放置不同的“晶石”来充能。祭司手里有 $N$ 种不同等级的晶石，每种等级的晶石都有无限多颗。第 $i$ 种晶石的法力值为 $v_i$。

由于能量过于集中容易引发爆炸，祭司希望在满足法力值恰好为 $M$ 的前提下，使用的晶石总数量越少越好。

请你计算出，达到目标法力值最少需要几颗晶石？如果无论如何都无法凑齐恰好 $M$ 的法力值，请输出 -1。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示晶石的种类和目标法力值。

接下来的 $N$ 行，每行包含一个整数 $v_i$，表示第 $i$ 种晶石的法力值。

输出格式

输出一个整数，表示最少需要的晶石数量。如果无法实现，输出 -1。

输入输出样例 #1

输入 #1

3 11
1
2
5

输出 #1

3

样例 1 说明

选择两颗法力值为 5 的晶石和一颗法力值为 1 的晶石，共 3 颗。虽然 5+2+2+2 也可以达到 11，但需要 4 颗，不是最少。

输入输出样例 #2

输入 #2

2 7
2
4

输出 #2

-1

数据范围

对于 $60\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 10^4$，$1 \le v_i \le M$。

建议

二刷