Migrated from Lutece 2546 众人拾柴火焰高

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

漫漫寒夜中，原始人家族快要被冻死了，但他们可以通过建起篝火来增加温度。原始人家族一共有 $n$ 个家庭，排成一列。第 $i$ 个家庭的初始温度为 $a_i$。

族长有 $m$ 堆篝火.

• 篝火可以放置在某个家庭，所有与该家庭距离小于等于 $x$ 的家庭都会受到此篝火影响，温度会上升 $k$。
• 同一个家庭可以放置多个篝火，所有家庭放置的篝火数量总和小于等于 $m$。
• 同一家庭受到多个篝火的影响时温度能叠加。即，若一个家庭受到 $c$ 堆篝火的影响，那么这个家庭的温度将变为 $a_i+ck$。

在族长决定篝火的归属权后，即将迎来寒潮。每轮寒潮会将所有家庭的温度降低 $1$，如果寒潮来临前，该家庭的温度已经等于 $0$，则他们会被冻死。

请问，族长最多可以保证坚持多少个寒潮而没有出现死亡的家庭。

Input

第一行四个正整数 $n,m,x,k$。

第二行 $n$ 个整数，第 $i$ 个非负整数表示 $a_i$。

Output

仅一行，表示答案。

Samples

5 2 1 2
4 4 2 4 4

6

Constraints

$1 \leq x \leq n \leq10^6$ $0 \leq m \leq 10^6$ $1 \leq k \leq 10^6$ $0 \leq a_i \leq 10^6$

Note

对于样例：篝火放置于第 $2,4$ 个家庭。所有家庭的温度都为 $6$。

Resources

2021 UESTC ICPC Training for Data Structures