2702: T4-随意发糖的 LEEZ
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：1
题目描述
LEEZ 老师有 $n$ 个学生，这些学生排成了一排，编号从 $1\sim n$。第 $i$ 个学生有 $a_i$ 颗糖。
LEEZ 老师希望让每个学生都至少有 $m$ 颗糖。初始的所有 $a_i$ 都小于 $m$。因此，他需要给学生发糖。
LEEZ 老师的发糖方式比较特殊，每次他可以任意挑选一个长度为 $k$ 的区间（比如 $a_1\sim a_k$ 或 $a_3\sim a_{k+2}$），并发出 $num$ 颗糖，这些糖可以随意分配给区间内的所有学生。
请问 LEEZ 老师**最少需要发几次**才能让所有学生都至少有 $m$ 颗糖。
LEEZ 老师希望让每个学生都至少有 $m$ 颗糖。初始的所有 $a_i$ 都小于 $m$。因此，他需要给学生发糖。
LEEZ 老师的发糖方式比较特殊，每次他可以任意挑选一个长度为 $k$ 的区间（比如 $a_1\sim a_k$ 或 $a_3\sim a_{k+2}$），并发出 $num$ 颗糖，这些糖可以随意分配给区间内的所有学生。
请问 LEEZ 老师**最少需要发几次**才能让所有学生都至少有 $m$ 颗糖。
输入
第一行四个整数 $n,m,k,num$。
接下来一行 $n$ 个整数，$a_1\sim a_n$。
接下来一行 $n$ 个整数，$a_1\sim a_n$。
输出
一行一个整数，表示答案。
样例输入 复制
4 10 2 6
1 2 3 4样例输出 复制
5提示
```input2
4 10 2 100
1 2 3 4
```
```output2
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 分）：没有特殊限制
4 10 2 100
1 2 3 4
```
```output2
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 分）：没有特殊限制