#A0409. 随意发糖的 LEEZ

随意发糖的 LEEZ

题目描述

LEEZ 老师有 nn 个学生,这些学生排成了一排,编号从 1n1\sim n。第 ii 个学生有 aia_i 颗糖。

LEEZ 老师希望让每个学生都至少有 mm 颗糖。初始的所有 aia_i 都小于 mm。因此,他需要给学生发糖。

LEEZ 老师的发糖方式比较特殊,每次他可以任意挑选一个长度为 kk 的区间(比如 a1aka_1\sim a_ka3ak+2a_3\sim a_{k+2}),并发出 numnum 颗糖,这些糖可以随意分配给区间内的所有学生。

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

输入格式

第一行四个整数 n,m,k,numn,m,k,num
接下来一行 nn 个整数,a1ana_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%100\% 的数据,1n,m,k,num,ai50001\le n,m,k,num,a_i \le 5000knk\le nai<ma_i\lt m

  • 子任务 1(30 分):保证 num=1num=1
  • 子任务 2(30 分):保证 k=1k=1
  • 子任务 3(40 分):没有特殊限制