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 翻译