/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個のカップがあり、それぞれのカップには無色透明な液体が入っています。
具体的には、i 番目 (1\leq i\leq N) のカップには A_i ml の液体が入っています。
また、これらのうちちょうど K 個のカップには日本酒が入っており、それ以外には水が入っていることが分かっています。
ただし、どのカップに日本酒が入っているかについては分かっていません。
高橋君は（1 つ以上の）いくつかのカップを選んでそれらに入った液体をすべて飲むことができます。
どのカップに日本酒が入っているかによらず、高橋君が確実に X ml 以上の日本酒を飲むためには、最低何個のカップを選ぶ必要があるか求めてください。
そのような選び方が不可能である場合には -1 を出力してください。
制約
- 1 \leq K \leq N \leq 3\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 3\times 10^{14}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X A_1 A_2 \ldots A_N
出力
条件をみたすために高橋君が選ぶ必要があるカップの個数の最小値を出力せよ。 そのような選び方が不可能である場合には -1 を出力せよ。
入力例 1
3 2 5 10 6 8
出力例 1
2
高橋君が 1 番目と 3 番目のカップを選んで飲んだ場合を考えます。
3 個のカップのうち 2 個に日本酒が入っているため、次の 3 通りが考えられます。
- 1,2 番目のカップに日本酒が入っていた場合
高橋君は 10 ml の日本酒と 8 ml の水を飲むことになります。
- 1,3 番目のカップに日本酒が入っていた場合
高橋君は 18 ml の日本酒を飲むことになります。
- 2,3 番目のカップに日本酒が入っていた場合
高橋君は 8 ml の日本酒と 10 ml の水を飲むことになります。
よって、いずれの場合でも 5 ml 以上の日本酒を飲むことができます。
一方で、どのカップに日本酒が入っているか分かっていない状態で、1 つのみのカップを選んで条件をみたすようにすることは不可能です。
よって、2 を出力します。
入力例 2
2 1 8 6 10
出力例 2
-1
1 番目のカップに日本酒が入っていた場合、どのようにカップを選んでも 8 ml 以上の日本酒を飲むことは不可能です。
よって、-1 を出力します。
入力例 3
5 3 3000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
5
Score : 300 points
Problem Statement
There are N cups, each containing a colorless and transparent liquid.
Specifically, the i-th (1\leq i\leq N) cup contains A_i ml of liquid.
It is known that exactly K of these cups contain sake (rice wine), and the rest contain water.
However, it is not known which cups contain sake.
Takahashi can choose some (one or more) cups and drink all the liquid in them.
Find the minimum number of cups he needs to choose to ensure he drinks at least X ml of sake, regardless of which cups contain sake.
If such a choice is impossible, print -1.
Constraints
- 1 \leq K \leq N \leq 3\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 3\times 10^{14}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K X A_1 A_2 \ldots A_N
Output
Print the minimum number of cups Takahashi needs to choose to satisfy the condition. If such a choice is impossible, print -1.
Sample Input 1
3 2 5 10 6 8
Sample Output 1
2
Consider the case where Takahashi chooses the first and third cups and drinks them.
Two out of the three cups contain sake, so the following three cases are possible:
- If the first and second cups contain sake
He drinks 10 ml of sake and 8 ml of water.
- If the first and third cups contain sake
He drinks 18 ml of sake.
- If the second and third cups contain sake
He drinks 8 ml of sake and 10 ml of water.
Thus, in all cases, he can drink at least 5 ml of sake.
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.
Therefore, print 2.
Sample Input 2
2 1 8 6 10
Sample Output 2
-1
If the first cup contained sake, it is impossible to drink 8 ml or more of sake no matter which cups are chosen.
Therefore, print -1.
Sample Input 3
5 3 3000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
5