A - Credits 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

京都大学では今期、N 個の講義が開講されており、進級には K 単位以上取得する必要があります。

i 番目の講義に割り当てられている単位数は a_i です。 あなたは最小限の履修で進級したいと考えています。 いくつの授業を履修する必要があるか求めてください。

制約

  • 1 \leq N \leq 50
  • 1 \leq K \leq 1,000
  • 1 \leq a_i \leq 20
  • N, K, a_i は整数である。

入力

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

N K
a_1 a_2 ... a_N

出力

必要な履修数の最小値を求めよ。 全ての講義を履修しても単位が足りない場合、代わりに -1 を出力せよ。

入力例1

5 15
3 8 2 5 6

出力例1

3

例えば、1, 2, 4 番目の講義を履修すれば良いです。

入力例2

5 25
3 8 2 5 6

出力例2

-1

全ての講義を履修しても単位が足りません。

入力例3

4 20
1 1 20 19

出力例3

1

Score : 100 points

Problem Statement

Kyoto University offers N lectures and you need more than or equal to K credits to advance to the next grade. You can earn a_i credits by taking i-th lecture. You want to take as small number of lectures as possible to advance to the next grade. How many lectures do you need to take?

Constraints

  • 1 \leq N \leq 50
  • 1 \leq K \leq 1,000
  • 1 \leq a_i \leq 20
  • N, K, a_i are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the minimum number of lectures to advance to the next grade. If you can not advance to the next grade even by taking all the lectures, print -1 instead.

Sample Input 1

5 15
3 8 2 5 6

Sample Output 1

3

For example, you can adcance to the next grade with first, second, and fourth lectures.

Sample Input 2

5 25
3 8 2 5 6

Sample Output 2

-1

You can not advance to the next grade even by taking all the lectures.

Sample Input 3

4 20
1 1 20 19

Sample Output 3

1

出典

KUPC2017