E. 我要打 k 个
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长为 $$$n$$$ 的数组 $$$a$$$ ，你当前拥有 $$$m$$$ 能量，你能做两种操作：

  1. 在 $$$a$$$ 数组中选择一个元素 $$$a_i$$$ 删除它，随后 $$$a_{i-1}$$$ 和 $$$a_{i+1}$$$ 变为相邻元素，这将花费 $$$a_i$$$ 能量;
  2. 选择数组 $$$a$$$ 中连续的 $$$k$$$ 个元素 $$$a_i,a_{i+1},a_{i+2},...,a_{i+k-1}$$$ 并删除，删除后 $$$a_{i-1}$$$ 和 $$$a_{i+k}$$$ 变为相邻元素；数组元素不足 $$$k$$$ 个则不能进行该操作，这个操作将花费 $$$x$$$ 能量。

若要删除的元素 $$$a_{i}$$$ 为数组唯一元素，则删除后数组为空。

若数组大小大于 $$$1$$$ 且 $$$a_i$$$ 位于数组最左侧，则删除后最左侧元素变为 $$$a_{i+1}$$$ 。

若数组大小大于 $$$1$$$ 且 $$$a_i$$$ 位于数组最右侧，则删除后最右侧元素变为 $$$a_{i-1}$$$ 。

你的剩余能量应当始终是非负的，请问你最多能删除几个 $$$a$$$ 数组中的元素？

Input

输入第一行包含四个正整数 $$$n,m,k,x$$$ $$$(1\le{k}\le{n}\le{2\times10^5},1\le{m,x}\le{10^9})$$$ ，分别代表 $$$a$$$ 数组初始元素个数，初始能量的大小，$$$k$$$ 和 $$$x$$$ 的含义见题目描述。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,...,a_n$$$ $$$(1\le{a_i}\le{10^9})$$$ ，代表 $$$a$$$ 数组。

Output

输出一个整数代表最多能删除的元素个数，

Example
Input
5 12 2 6
6 4 1 5 9
Output
4
Note

对于样例，你可先使用一操作删除 $$$a_{3}=1$$$ ，花费 $$$1$$$ ，随后数组变为 $$$\{6,4,5,9\}$$$ ，然后再使用一次二操作删除 $$$a_{1}=6,a_{2}=4$$$ ，花费 $$$x=6$$$ ，随后数组变为 $$$\{5,9\}$$$ ，然后使用一次一操作删除 $$$a_{1}=5$$$ ，随后数组变为 $$$\{9\}$$$ ，花费 $$$5$$$ 。