给定一个长为 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 数组中的元素？

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

第二行包含 n 个正整数 a1,a2,...,an (1≤ai≤10^9) ，代表 a 数组。