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}$ - 所有输入值均为整数。