C - Minimum Number of Items to Buy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はスーパーマーケットに買い物に来ています。棚には N 個の商品が一列に並んでおり、左から i 番目の商品の価格は A_i 円です。それぞれの商品は 1 個ずつしかありません。

高橋君は、これらの商品の中からいくつかを選んでカゴに入れようとしています。各商品について「選ぶ」か「選ばない」かを決め、選んだ商品の価格の合計がちょうど 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
  • 1 行目には、商品の個数を表す N と、目標の合計金額を表す S が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

選んだ商品の価格の合計をちょうど S 円にできる場合は、選ぶ商品の最小個数を 1 行で出力せよ。不可能な場合は -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

Score : 366 pts

Problem Statement

Takahashi is shopping at a supermarket. There are N items lined up in a row on the shelf, and the price of the i-th item from the left is A_i yen. There is only one of each item.

Takahashi wants to select some of these items and put them in his basket. For each item, he decides whether to "select" it or "not select" it, and he wants the total price of the selected items to be exactly S yen.

However, Takahashi wants to achieve a total of exactly S yen with as few items as possible.

Determine whether it is possible to make the total price of the selected items exactly S yen. If it is possible, output the minimum number of items to select. If it is impossible, output -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq S \leq 10000
  • 1 \leq A_i \leq 10000 (1 \leq i \leq N)
  • All inputs are integers

Input

N S
A_1 A_2 \ldots A_N
  • The first line contains N, representing the number of items, and S, representing the target total price, separated by a space.
  • The second line contains the prices of each item A_1, A_2, \ldots, A_N, separated by spaces.

Output

If it is possible to make the total price of the selected items exactly S yen, output the minimum number of items to select on a single line. If it is impossible, output -1.

Sample Input 1

5 10
3 5 7 2 8

Sample Output 1

2

Sample Input 2

4 11
3 6 9 12

Sample Output 2

-1

Sample Input 3

15 100
12 50 25 7 33 18 50 44 9 61 15 73 28 36 42

Sample Output 3

2