【题目描述】

古老的 A 国爆发了一场瘟疫。
A 国有 $n$ 座城市，从 $1$ 到 $n$ 编号，这场瘟疫对第 $i$ 座城市有一个适应度 $a_i$，这个值越大，瘟疫对这座城市造成的伤害就越大。
这 $n$ 座城市的排布可以视作一条直线，于是对于 $1 < i < n$，$i$ 号城市和 $i − 1$ 号城
市与 $i + 1$ 号城市相邻；$1$ 号城市仅与 $2$ 号城市相邻；$n$ 号城市仅与 $n − 1$ 号城市相邻。
这场瘟疫初始在至多 $m$ 座城市里爆发，一座被瘟疫感染的城市有可能把瘟疫扩散到
与其相邻的城市。一场瘟疫的最终适应度是其感染的每座城市的适应度之和。
具体的扩散情况没有被记录，你想知道这场瘟疫可以带来的最大的伤害，即它能达成的最大的最终适应度。
注意，适应度 $a_i$ 可以是负数，瘟疫也可能初始不感染任何一座城市。

【输入格式】

从文件 $plague.in$ 中读入数据。
第一行两个整数 $n$, $m$。
第二行 n 个整数 $a{_{1}{_{\cdots}{_n}}}$。

由于本题输入量较大，我们在对应文件夹内下发了 IO.cpp。注释的两行仅能在使用 文件读入输出时使用，但会大大加快读入速度。

【输出格式】

输出到文件 $plague.out$ 中。 一行一个整数表示答案。

【样例 1 输入】

5 3    
1 ‐1 1 ‐1 1

【样例 1 输出】

3

【样例 1 解释】

当瘟疫初始在第 $1, 3, 5$ 座城市爆发，都不向相邻城市扩散时取得最大适应度 $1 + 1 + 1 = 3$。

【样例 2、3】

见 /ex_plague2.in、/ex_plague3.in 与 /ex_plague2.out、/ex_plague3.out。

【测试点约束】

对于所有测试点，$1 ≤ m ≤ n ≤ 6 × 10^6，|ai| ≤ 10^8。$
每个测试点的具体限制见下表：