次元波动平衡

题目描述

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

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

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

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

$$\max_{1 \leq i \leq j \leq n} \sum_{k=i}^ja\prime_k$$

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

输入格式

第一行包含三个整数 $n、K$ 和 $D$ ，其中 $n$ 表示未来可以预测的时间点数量，$K$ 表示 你能进行干预的最大次数，$D$ 是你的次元调谐器的削减量。$(1≤n≤5×10^5，0≤K≤n;1≤D≤10^9)$

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

输出格式

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

样例 #1

样例输入 #1

5 2 2
1 ‐2 3 1 1

样例输出 #1

1

提示

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