AT_tkppc4_1_p.Flip Cards

有一天，sanada 被 kaage 要求抽取 $N$ 张卡牌。
sanada 按照要求抽取了卡牌。
每张卡牌的正反两面分别写有一个数字，且两面数字之和恒为 $M$。sanada 抽到的第 $i$ 张卡牌正面上的数字为 $A_i$。

接下来，kaage 指示可以进行不超过 $K$ 次（也可以不进行）的如下操作：

• 任选满足 $1 \leq x \leq y \leq N$ 的整数 $x, y$，将第 $x$ 张到第 $y$ 张所有卡牌的正反面全部翻转。

sanada 觉得可疑，于是派间谍去 kaage 家，得知卡牌正面数字之和越大，kaage 就要学习得越多。
为了让 kaage 多学习，sanada 想知道通过适当次数和适当的操作，所有卡牌正面数字之和的最大值是多少。

输入以如下格式从标准输入读入：

$N$ $M$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

输出通过适当次数和操作后，所有卡牌正面数字之和的最大值，输出一行。

限制

• 输入均为整数。
• $1 \leq N \leq 10^6$
• $0 \leq K \leq N$
• $1 \leq M \leq 10^9$
• $1 \leq A_i \leq M-1$

小任务

本题包含 $3$ 个小任务。

1. (400 分) $N \leq 2000$
2. (400 分) $N \leq 10^5$
3. (300 分) 无额外限制。

注意

如果只针对小任务 $1$ 编写代码，建议在 $N > 2000$ 时立即退出。

样例解释 1

在这种情况下，例如一次操作都不进行时，所有卡牌正面数字之和最大为 $10$。

样例解释 2

例如可以通过如下区间选择和操作，得到最大值 $52$。

• 第 $1$ 次：翻转第 $1$ 张到第 $5$ 张卡牌。操作后卡牌为 {$8,\ 6,\ 1,\ 2,\ 4,\ 3,\ 5,\ 1$}。
• 第 $2$ 次：翻转第 $3$ 张到第 $8$ 张卡牌。操作后卡牌为 {$8,\ 6,\ 8,\ 7,\ 5,\ 6,\ 4,\ 8$}。

由 ChatGPT 4.1 翻译