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

题目描述

端午节到了，可爱的 LU 老师要给集训队员发粽子

集训队一共有 $n$ 个学生，这些学生排成了一排，编号从 $1\sim n$。第 $i$ 个学生有 $a_i$ 只粽子。

LU 老师希望让每个学生都至少有 $m$ 只粽子。初始的所有 $a_i$ 都小于 $m$。因此，他需要给学生发粽子。

LU 老师的发粽子方式比较特殊，每次他可以任意挑选一个长度为 $k$ 的区间（比如 $a_1\sim a_k$ 或 $a_3\sim a_{k+2}$），并发出 $num$ 只粽子，这些粽子可以随意分配给区间内的所有学生。

请问 LU 老师最少需要发几次才能让所有学生都至少有 $m$ 只粽子。

输入格式

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

接下来一行 $n$ 个整数，$a_1\sim a_n$。

对于 $100\%$ 的数据，$1\le n,m,k,num,a_i \le 5000$ 且 $k\le n$，$a_i\lt m$。

输出格式

一行一个整数，表示答案。

样例

4 10 2 6
1 2 3 4

5

4 10 2 100
1 2 3 4

2

样例解释

样例1：

• 第一步：给 [1 2] 3 4 发，变成 [7 2] 3 4
• 第二步：给 [7 2] 3 4 发，变成 [10 5] 3 4
• 第三步：给 10 [5 3] 4 发，变成 10 [10 4] 4
• 第四步：给 10 10 [4 4] 发，变成 10 10 [7 7]
• 第五步：给 10 10 [4 4] 发，变成 10 10 [10 10]