该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述

小青发明了一种神奇药水，喝下药水的人每天头发都会长 $x$ 厘米。

现在有 $n$ 个人参加实验，第 $i$ 个人原来的头发长度为 $a_i$ 厘米。
小青想知道：最早在第几天时，至少有 $k$ 个人的头发长度严格超过 $y$ 厘米。

注意：

• 第 $0$ 天时，头发长度仍然是原来的长度；
• 经过 $d$ 天后，第 $i$ 个人的头发长度为 $a_i + d \times x$。

输入

第一行输入四个整数 $n,k,x,y$。$(1 \leq n \leq k \leq 10^6,1 \leq x,y \leq 10^9)$
第二行输入 $n$ 个整数，$a_1,a_2,\dots,a_n$。$(1 \leq a_i \leq 10^9)$

输出

输出一个整数，表示最早满足条件的天数。

输入输出样例 #1

输入

5 3 2 10
1 2 3 4 5

输出

4