问题描述

有 $N$ 个杯子，每个杯子装有 $A_i$ 毫升无色透明液体（清酒或水）。

正好 $K$ 个杯子装清酒，其余装水，但具体哪些不知道。高桥选择若干个（一或多个）杯子并喝光。

求在保证无论哪些杯子装清酒他都至少喝 $X$ 毫升清酒的前提下，他最少需要选择多少个杯子。若无法做到，输出 $-1$。

输入格式

第一行包含三个整数 $N, K, X$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

输出格式

一个整数，即最少需要选择的杯子数；若无法做到，输出 $-1$。

样例输入 1

3 2 5
10 6 8

样例输出 1

2

说明：选第 1 和第 3 杯。无论哪两杯是清酒，他喝到的清酒至少 $8$ 毫升（$K=2$, $N-m=1$，选中必须含 $1$ 个清酒，最坏在选中的最小杯 $8$ 毫升）。只选 1 杯最坏可能是水，喝 $0$ 毫升。最少需要 $2$ 个杯子。

样例输入 2

2 1 8
6 10

样例输出 2

-1

说明：选 $1$ 杯最坏是水（喝 $0$ 毫升）；选 $2$ 杯全选（$K=1$, $N-m=0$, 选中必须含 $1$ 个清酒，最坏在最小杯 $6$ 毫升），$6 < 8$。无论选几个杯子，最坏喝到的清酒都不足 $8$ 毫升。

样例输入 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 3

5

说明：$K=3$, 全选 $5$ 杯时 $N-m=0$ 选中必须含 $3$ 个清酒，最坏在最小 3 个杯子（各 $10^9$），喝 $3 \times 10^9 \ge 3 \times 10^9$。选 $4$ 杯时 $N-m=1$ 选中必须含 $2$ 个清酒，最坏在最小 $2$ 个选中的杯子（$10^9 + 10^9 = 2 \times 10^9 < 3 \times 10^9$）。故最少需选 $5$ 杯。

评测数据规模

对于所有数据，保证 $1 \le K \le N \le 3 \times 10^5$，$1 \le A_i \le 10^9$，$1 \le X \le 3 \times 10^{14}$。