题目描述

公元 11 世纪初，有一些被称为维京人的丹麦入侵者在英格兰活动。

Askeladd 是一群维京海盗的领袖，他在这片肥沃的土地上寻找宝藏。在一夜袭击了一个村庄后，他们共收集了 $n$ 个宝藏，按顺序排列，价值分别为$a_1, a_2, \ldots, a_n$。 Askeladd 的团队有一项关于如何分配这些宝藏的协议：作为领袖的 Askeladd 将取走前面的k个宝藏，即价值为 $a_1, a_2, \ldots, a_k$ 的宝藏，而其余海盗将分配其余的宝藏。但是，由于时间太晚，他们决定在第二天早上进行这个分配。

Askeladd 非常聪明且狡猾，他在夜间偷偷摸摸地试图重新安排宝藏，以便他可以获得更多的宝藏总价值。然而，由于某种原因，他只被允许交换两个相邻的宝藏。此外，考虑到被其他海盗发现的风险，每次交换将花费 Askeladd $c$ 的价值。Askeladd 可以执行任意数量（可能为零）的交换。

Askeladd 想知道他可以获得的最大利润是多少（即他可以获得的所有宝藏总价值减去交换所消耗的总代价）。

输入格式

第一行包含三个整数 $n, k$ 和 $c$ ($0 \leq k \leq n \leq 3 \times 10^5, 0 \leq c \leq 10^9$)，表示宝藏的总数量，Askeladd 取走的宝藏数量，以及交换相邻两个宝藏的成本。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)，表示宝藏的价值。

输出格式

在一行中输出一个整数，表示 Askeladd 能获得的最大利润。

3 2 1
1 3 5

6

解释 #1

为了帮助理解，我们提供了第一个样例的说明。当 Askeladd 不进行任何交换时，他获得的总利润等于 $4$。

Askeladd 的最佳方法是交换第一个和第二个宝藏，然后交换第二和第三个宝藏，总利润为 $6$。

3 2 2
1 3 5

4

4 2 1
2 3 5 6

7

7 3 2
2 1 3 6 10 9 7

10