AT_abc441_c [ABC441C] Sake or Water
题目描述
有 $N$ 个杯子,每个杯子都装有一种无色透明的液体。
具体来说,第 $i$ 个杯子 $(1\leq i\leq N)$ 中有 $A_i$ 毫升液体。
众所周知,这些杯子中正好有 $K$ 个装的是清酒(米酒),其余的装的是水。但是,不知道哪些杯子装的是清酒。高桥可以选择一些(一个或多个)杯子,喝掉其中的所有液体。
求无论哪些杯子装有清酒,在保证他至少喝 $X$ 毫升清酒的前提下,他至少需要选择多少个杯子? 如果无法选择,请输出 $-1$ 。
输入格式
输入内容由标准输入提供,格式如下:
>$N$ $K$ $X\\$
$A_1$ $A_2$ $\ldots$ $A_N$
输出格式
打印高桥为满足条件而需要选择的最少杯子数。如果无法选择,则输出 $-1$ 。
说明/提示
#### 样例解释 #1
考虑高桥选择第一杯和第三杯并喝下它们的情况。
三个杯子中有两个装的是清酒,因此可能出现以下三种情况:
- 如果第一杯和第二杯都有清酒
他喝了 $10$ 毫升清酒和 $8$ 毫升水。
- 如果第一杯和第三杯装的是清酒
他喝 $18$ 毫升清酒。
- 如果第二和第三杯有清酒
他喝 $8$ 毫升清酒和 $10$ 毫升水。
因此,在所有情况下,他至少可以喝 $5$ 毫升清酒。
另一方面,在不知道哪些杯子装清酒的情况下,只选择一个杯子是不可能满足条件的。因此,输出 $2$ 。
#### 样例解释 #2
如果第一杯装的是清酒,那么无论选择哪一杯,都不可能喝下 $8$ 毫升或更多的清酒。
因此,输出 $-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}$
- 所有输入值均为整数。