You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 老师有 $n$ 个学生，这些学生排成了一排，编号从 $1\sim n$。第 $i$ 个学生有 $a_i$ 颗糖。

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

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

请问 Csvoner 老师最少需要发几次才能让所有学生都至少有 $m$ 颗糖。

输入格式

第一行四个整数 $n,m,k,num$。
接下来一行 $n$ 个整数，$a_1\sim a_n$。

输出格式

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

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]

数据规模与约定

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

• 子任务 1（30 分）：保证 $num=1$
• 子任务 2（30 分）：保证 $k=1$
• 子任务 3（40 分）：没有特殊限制