501000042 - 早凉与序列4

早凉给你一个长度为 n 的整数序列 a_1, a_2, \cdots , a_n。

早凉很喜欢两个整数 k,x。早凉想要选择恰好 k 个位置，让这些位置的值加上 x，其余的位置减去 x。

在执行完上述操作后，早凉会选择两个正整数 l,r(1\leq l,r\leq n)，之后计算 S=a_{l}+a_{l+1}+\cdots+a_r。特别的，若 l>r，则 S=0。

你需要帮助早凉算出， S 能取到的最大值是多少。

早凉只用 \text{40ms} 就算出来了，你能教她一个更优解吗？

第一行三个整数 n,k,x。

第二行 n 个整数，第 i 个为 a_i。

一个整数表示答案。

样例1说明

我们选择第 4 个数，序列变成 (0,-3,0,5)，选 l=4,r=4 时 S=a_4=5。

数据范围及约定

2\leq n\leq 2\times10^5,0\leq k\leq n,-10^9\leq x\leq 10^9,-10^9\leq a_i\leq 10^9。