时间限制： 1.5 秒

空间限制： 512 MB

题目描述

欢迎来到异次元世界的波动预测局（也被称为“未来视窗”）！在这里，我们有一台神奇的仪器——时间风波镜。它能预测到次元能量指数未来 $n$ 个时间点的波动。这组波动用数学表示为 $A=a_1,a_2,\cdots,a_n$。

不过别高兴太早，事情并不那么简单。由于暗黑神力的影响，波动可能异常剧烈，甚至有可能引发次元风暴！

但别担心，你作为一名波动调节师（还有着二次元头像的那种），有权在不超过 $K$ 个时间点上使用你的神秘力量——次元调谐器进行干预。次元调谐器能让你选择在某个时间点的波动值减去 $D$。注意，一个时间点最多可以被干预 $1$ 次。

你的任务，如果选择接受的话，是通过合理地选择最多 $K$ 个时间点进行干预，从而最小化“次元波动指数”，次元波动指数是指未来任意时间段的波动之和的最大值。具体来说你需要最小化：

$$\max\limits_{1\le i\le j\le n} \sum\limits_{k=i}^j a_k' $$

其中 $a_k'$ 是在对波动数组 $A$ 做至多 $K$ 次干预后得到的数组 $A'$ 中的波动值。

输入格式

从标准输入读入数据。

第一行包含三个整数 $n,K,D$，其中 $n$ 表示未来可以预测的时间点数量，$K$ 表示你能进行干预的最大次数，$D$ 是你的次元调谐器的削减量。

第二行包含 $n$ 个整数 $a_i$，表示预测到的次元能量指数在未来 $n$ 个时间点的波动。

输出格式

输出到标准输出。

输出一个整数，表示通过至多 $K$ 次干预后的最小次元波动指数。

5 2 2
1 -2 3 1 1

1

样例 1 解释

选择第 $3$ 和第 $4$ 个时间点干预，得到干预后的数组 $A'$ 为 $\{1,-2,1,-1,1\}$，它的次元波动指数是 $1$。

12 4 56
1 9 8 -6 1 8 12 10 16 17 -4 -5

10

31 5 26
-41 7 15 37 14 -43 33 -8 -48 28 -47 22 17 -33 20 4 8 38 -11 8 3 49 -23 39 -8 27 -32 23 -13 -47 -21

56

子任务

对于所有的数据，满足 $1\le K\le n\le 5\times 10^5,~1\le D\le 10^9,~-10^9\le a_i\le 10^9$。默认数据随机生成，部分子任务数据基于特殊构造。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

此外，本题中子任务向前依赖，即只有当前一个子任务全部通过时，下一个子任务才会开始评测。

子任务编号	分值	$n\le$	$K\le$	包含特殊构造
1	10	$10^2$	$3$	$\times$
2		$10^3$
3	20	$10^4$
4		$10^5$
5				$\checkmark$
6		$5\times 10^5$