在通往世界总决赛的征途中，秀知院学园战队需要首先征服北美冠军赛。题集中共有 $n$ 道题，解决第 $i$ 道题需要 $s_i$ 分钟。秀知院学园战队可以按任意顺序解题，但不能并行（同时）解题。这意味着他们必须先解决当前正在做的题，然后才能开始解决另一道题。每解决一道题，裁判会立即给队伍送来一个充饱气的气球。

队伍中的恶作剧担当藤原千花决定将所有的气球系在队伍的幸运骰子上，好让它漂浮起来。每个气球在队伍收到时都含有 $1$ 升氦气，可以提供 $1$ 克的升力。所有气球的寿命均为 $d$。气球以每分钟 $\frac{1}{d}$ 升的恒定速率漏气，其升力（以克为单位）也以相同的速率减少；例如，一个气球在 $\frac{d}{3}$ 分钟后可以提供 $\frac{2}{3}$ 克的升力，并在 $d$ 分钟后减少到 $0$ 克。如果在任意时刻，队伍拥有的所有气球的升力之和大于或等于骰子的质量 $m$，骰子就会漂浮起来。气球自身的质量可以忽略不计。

给定一个包含 $n$ 道题的题集，其中第 $i$ 道题的解题时间为 $s_i$，以及气球寿命 $d$ 和骰子质量 $m$，输出秀知院学园战队为了让骰子漂浮起来所需要解决的最少题目数量。如果无法让骰子漂浮，则输出 $-1$。

输入格式

输入的第一行包含三个整数 $n$、$d$ 和 $m$（$1 \le n, d, m \le 10^5$），分别表示题集的题目数量、气球的寿命以及骰子的质量。

输入的第二行包含 $n$ 个整数：解题时间 $s_1$ 到 $s_n$（$1 \le s_i \le 10^5$）。

输出格式

输出一个整数：秀知院学园战队为了让骰子漂浮起来所需要解决的最少题目数量，如果不可能实现，则输出 $-1$。

样例

输入样例 1

3 4 2
1 5 2

输出样例 1

3

输入样例 2

4 5 2
1 2 4 6

输出样例 2

3

输入样例 3

5 14 3
1 2 4 6 8

输出样例 3

4

输入样例 4

5 12 3
2 2 3 3 4

输出样例 4

5

输入样例 5

5 10 3
2 2 3 3 4

输出样例 5

-1