时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。

你可以对该序列进行最多 $m$ 次操作。一次操作如下：选择一个 $x$ 满足 $1 \le x < n$，使 $a_{x+1}:=a_{x+1}+a_x$，然后使 $a_x:=0$（“$:=$”表示赋值）。

请你求出进行最多 $m$ 次操作后，$a_1,a_2,\dots,a_n$ 中的最大值最大是多少。

格式

输入格式

第一行包含两个正整数 $n, m$，表示序列长度和最多操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示序列 $a$。

输出格式

输出一行一个整数，表示答案。

样例

样例输入 #1

5 2
-4 3 -1 5 1

样例输出 #1

7

样例解释 #1

进行如下 $2$ 次操作：

第 $1$ 次操作，选择 $x=3$，操作后序列 $a$ 变为 $[-4,0,2,5,1]$。

第 $2$ 次操作，选择 $x=4$，操作后序列 $a$ 变为 $[-4,0,0,7,1]$。

操作后序列 $a$ 的最大值为 $7$，可以证明没有操作方案能使得操作后序列 $a$ 的最大值大于 $7$。

样例输入 #2

8 4
-5 2 3 1 -2 4 2 1

样例输出 #2

8

样例输入 #3

4 2
-6 2 5 -1

样例输出 #3

7

样例输入 #4

4 2
-5 -2 -6 -3

样例输出 #4

0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$
$1$	$30$	$500$
$2$	$70$	$5000$

对于 $100\%$ 的数据，$1 \le m \le n \le 5000$，$\lvert a_i \rvert \le 10^5$。