分数: 366 分
问题陈述
高桥正在超市购物。有 N 商品在货架上排成一排,以及该商品的价格 i左起第一项是 A_i 日元。每个项目只有一个。
高桥想要选择其中一些物品并将其放入他的篮子中。对于每个商品,他决定“选择”它还是“不选择”它,并且他希望所选商品的总价恰好是 S 日元。
然而,高桥希望总共达到 S 日元,物品尽可能少。
判断是否可以使所选商品的总价精确 S 日元。如果可能,输出要选择的最少项目数。如果不可能,则输出 -1.
约束
- 1 \leq N \leq 100
- 1 \leq S \leq 10000
- 1 \leq A_i \leq 10000 (1 \leq i \leq N)
- 所有输入均为整数
输入
N S A_1 A_2 \ldots A_N
- 第一行包含 N,代表项目数量,以及 S,代表目标总价,以空格分隔。
- 第二行包含每件商品的价格 A_1, A_2, \ldots, A_N,用空格分隔。
输出
是否可以准确计算所选商品的总价 S 日元,输出单行中要选择的最少项目数。如果不可能,则输出 -1.
示例输入 1
5 10 3 5 7 2 8
示例输出 1
2
示例输入 2
4 11 3 6 9 12
示例输出 2
-1
示例输入 3
15 100 12 50 25 7 33 18 50 44 9 61 15 73 28 36 42
示例输出 3
2