← 返回题目列表

AtCoder · awc0077_c

C. 购买的最少商品数量

中文机器翻译题面 查看原题

分数: 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