Time Limit: 1 sec / Memory Limit: 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