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.

T2星际旅行

时间限制：$2s$

空间限制：$512MB$

题目描述

在遥远的未来，人类已经掌握了星际旅行的技术。你是一名星际探险家，驾驶着你的飞船穿梭于银河系之间，探索未知的星球和文明。在一次探险中，你发现了一个神秘的古老遗迹，这个遗迹似乎是由一个早已消失的高级文明建造的。

遗迹内部有一个复杂的控制系统，由一系列能量节点组成，这些节点排列成一条直线。每个节点的能量值可以用一个整数表示，这些值存储在一个数组 $a_1, a_2, ..., a_n$中。你还发现了两个神秘的参数 $k$和 $x$，它们似乎是控制这些能量节点的关键。

你的任务是执行一次特殊的能量调整操作：将 $x$单位的能量加到恰好 $k$个不同位置的节点上，并从所有其他节点中减去 $x$ 单位的能量。

定义函数 $f(a)$ 表示调整后数组 $a$的子数组的最大可能和。这里的子数组是指数组 $a$中连续的一部分，即对于某些 $1 \leq i \leq j \leq n$，子数组可以表示为 $a_i, a_{i+1}, ..., a_j$。需要注意的是，空子数组也被视为一种情况，其和为 0。

现在，设数组 $a'$是应用上述操作后的结果。你需要以这样的方式应用操作，使得 $f(a')$达到最大值，并输出这个最大值。

在这个场景中，你可以想象自己是一名星际探险家，正在尝试激活这个古老遗迹的隐藏功能。通过精确地调整特定节点的能量，你的目标是找到能够最大化连续节点总能量的最佳策略。这不仅考验你的数学能力，也考验你在面对未知文明技术时的智慧和勇气。

输入格式

第一行包含三个整数 $n$，$k$ 和 $x$$（1≤n≤2⋅10^5; 0≤k≤n; −10^9≤x≤10^9）$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$$(−10^9≤a_i≤10^9)$。

输出格式

共一行，一个整数，表示最大化连续节点总能量

样例输入

4 1 2
2 -1 2 3

样例输出

5

数据范围