【题目描述】
古老的 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。$
每个测试点的具体限制见下表:
测试点编号 | $n ≤$ | 分值 |
---|---|---|
1 | $500$ | 10 |
2 | $5000$ | 10 |
3 | $5000$ | 10 |
4 | $10^5$ | 15 |
5 | $10^5$ | 15 |
6 | $6*10^6$ | 40 |