秽土斑（Hard Version）

题号：NC297614
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

突然，斑加入战场，横扫忍者联军后，对战五影。
面对五影的挑衅，他决定戏耍五影。

本题的Easy Version 和 Hard Version 唯一的区别只有数据范围。

他召唤出 $n$ 个须佐，成环形放置，每个须佐都有一个分数，第 $i$ 个须佐的分数为 $w_i$ （ $1 \leq i \leq n$ ）。

一开始，五影的分数 $G = 0$ ，并且我们令 $n_1 = n$ 。

现在需要五影做 $m$ 轮决策。我们以第 $j$ 轮（ $1 \leq j \leq m$ ）的决策为例：

1. 对当前总数为 $n_j$ 的环形须佐，我们从中选择连续的一段须佐消灭，数量为 $cnt_j$ （ $0 \leq cnt_j \leq n_j$ ）；
2. 将这 $cnt_j$ 个须佐的分数加到 $G$ 上，同时将剩下的 $n_j - cnt_j$ 个须佐按照之前的相对顺序重新拼接成环；
3. 令 $n_{j + 1} = n_j - cnt_j$ 。

请问五影要怎么决策才能最大化分数 $G$ ？由于他们都被斑的气势吓到了，所以想请你快速地来解答一下这个问题。

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。

输入描述:

第一行输入两个整数 ，分别表示一开始的须佐数量、进行的决策次数。
第二行输入  个空格隔开的整数，表示  个须佐的分数 。

输出描述:

输出最后的最大分数 。

示例1

输入

复制

5 1
-9 1 2 3 -2

输出

复制

说明

五影可以选择中间的  得到  分。

示例2

输入

复制

5 1
1 1 -1 1 1

输出

复制

说明

五影可以获得  分。

示例3

输入

复制

4 4
-2 -2 -2 -2

输出

复制

说明

五影可以一直不选，保持 。