秽土斑(Easy Version)
题号:NC296357
时间限制: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_i1 \leq i \leq n)。

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

现在需要五影做 m 轮决策。我们以第 j 轮(1 \leq j \leq m)的决策为例:

1. 对当前总数为 n_j 的环形须佐,我们从中选择连续的一段须佐消灭,数量为 cnt_j0 \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。

输入描述:

第一行输入两个整数 n, m \ (1 \leq m \leq n \leq 5000),分别表示一开始的须佐数量、进行的决策次数。
第二行输入 n 个空格隔开的整数,表示 n 个须佐的分数 w_i \ (-10^9 \leq w_i \leq 10^9)

输出描述:

输出最后的最大分数 G
示例1

输入

复制
5 1
-9 1 2 3 -2

输出

复制
6

说明

五影可以选择中间的 1, 2, 3 得到 6 分。
示例2

输入

复制
5 1
1 1 -1 1 1

输出

复制
4

说明

五影可以获得 4 分。
示例3

输入

复制
4 4
-2 -2 -2 -2

输出

复制
0

说明

五影可以一直不选,保持 G = 0