分数: 300 点
问题陈述
有 N 杯子,每个杯子里盛着无色透明的液体。
具体来说, i-th (1\leq i\leq N) 杯子包含 A_i 毫升液体。
众所周知,正是 K 这些杯子里盛的是清酒(米酒),其余的杯子里盛的是水。
然而,不知道哪些杯子里装有清酒。
高桥可以选择一些(一个或多个)杯子并喝掉其中的所有液体。
找出他需要选择的最少杯子数量,以确保他至少喝完 X 毫升清酒,无论哪个杯子盛有清酒。
如果这样的选择不可能,则打印 -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
考虑高桥选择第一杯和第三杯并喝掉它们的情况。
三个杯子中有两个装有清酒,因此可能存在以下三种情况:
- 如果第一杯和第二杯含有清酒
他喝酒 10 毫升清酒和 8 毫升水。
- 如果第一杯和第三杯含有清酒
他喝酒 18 毫升清酒。
- 如果第二杯和第三杯含有清酒
他喝酒 8 毫升清酒和 10 毫升水。
因此,在所有情况下,他至少可以喝 5 毫升清酒。
另一方面,在不知道哪些杯子装有清酒的情况下仅选择一个杯子是不可能满足条件的。
因此,打印 2.
示例输入 2
2 1 8 6 10
示例输出 2
-1
如果第一杯里有清酒,则无法饮用 8 毫升或更多的清酒,无论选择哪个杯子。
因此,打印 -1.
示例输入 3
5 3 3000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
5