E - Break-The-Brick !

2 secs 1024 MB
matcharate12's icon matcharate12

※この問題で Python 言語を用いる方は極力、提供されている Python 言語のコンパイル種類である pypy を選んで提出してください。CPython を選んで提出すると、実装方法によっては TLE になる可能性があります。

Story

🔨

ついに看板メニューが完成しました!!
このパンケーキはおいしすぎたので、matcharate君たちは早速この茶屋で過ごすお客さんに提供することにしました。

とりあえず仕事が落ち着いたmatcharate君たちは、ため息をつきながら椅子に横たわりました。するとそこへ、num168君という常連さんはこう言ってきました。

"こうやって話すのは久しぶりだね。どうだ?私と一緒に、何かゲームをしないかい?"

matcharate君たちは急な話すぎて理解が追いついていませんでしたが、num168君は颯爽と積み木とペン、そして木の小さなハンマーをバッグから取り出しました。そしてnum168はこう言いました。

"今から積み木に何か数字を書くから、私が言う質問に対し、よくある「ダルマ落とし」のようにハンマーを使って落としておくれ!!"

よくわからないですが、なんだか楽しそうだったのでmatcharate君は仕方なく付き合ってあげました。

問題

NN 個の積み木が重なっています。そのうち上から i (1iN)i\ (1\le i\le N) 番目の積み木には整数 AiA_i が書かれていました。

matcharate君は木の小さなハンマーを持っています。
このハンマーを用いてこの積み重なった積み木からいくつか選び( 11 つも選ばなくても構いません)、その選んだ積み木をうまく落とします。
この操作の後で、num168君は残った積み木に書かれた整数の和がちょうど SS になるようにしたいと思っています。

matcharate君が目標を達成させるような積み木の落とし方は存在しますか?存在するなら、落とす積み木の個数の最小値を求めてください。
ただしすべての積み木を落とした時、結果となる総和は 00 であるとします。

入力

入力は以下の形式で与えられる。

NNSS
A1A_1A2A_2\dotsANA_N

制約

  • 1N5001\le N\le 500
  • 0S5×1040\le S\le 5\times 10^4
  • 1Ai1001\le A_i\le 100
  • 入力はすべて整数

出力

目標を達成できるような積み木の落とし方が存在するなら落とす積み木の個数の最小値を、存在しないなら -1 を出力せよ。

入出力例

入力例1
5 6
1 2 3 4 5
出力例1
2

例えば上から 4,54,5 番目の 22 つの積み木を落とすと、残った積み木に書かれている整数の総和は 1+2+3=6(=S)1+2+3=6(=S) となり、条件を満たします。
11 つ以下で条件を満たす操作方法は存在しません。

入力例2
5 16
1 2 3 4 5
出力例2
-1

どのように操作をしても、最初の状態では 1+2+3+4+5=151+2+3+4+5=15 より条件を満たす操作方法は存在しません。

入力例3
3 0
1 1 1
出力例3
3

すべての積み木を落とすことで条件を満たすこともあります。

入力例4
11 10
3 1 4 1 5 9 2 6 5 3 5
出力例4
6

提出


Go (1.21)