该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

有 $n$ 个史莱姆排成一行，每个史莱姆都有一个战力 $a_i$。

每只史莱姆可以“吞并”其左边的那只，并获取他的战力：$a_i\leftarrow a_i+a_{i-1}$，并且左边的那只就会消失。

现执行 $m$ 次“吞并”操作后，战力最高的那只史莱姆是多少？

输入格式

第一行，$2$ 个正整数，$n,m$ 分别表示史莱姆的总数、吞并操作的总次数

第二行，$n$ 个正整数 $a_i$，表示每个史莱姆的战力

输出格式

一个整数，表示 $m$ 次吞并操作后，史莱姆最高的战力值

输入输出样例

7 3
1 5 2 5 3 4 1

15

样例 $\tt \#1$说明

第一次合并，合并第3和第4只史莱姆，史莱姆力量变成了：1 5 7 3 4 1。

第二次合并，合并第2和第3只史莱姆，史莱姆力量变成了：1 12 3 4 1。

第三次合并，合并第2和第3只史莱姆，史莱姆力量变成了：1 15 4 1。

三次合并后，史莱姆的最大力量是 15。 可以证明 15 是能达到的最大力量。

数据范围

$50\%:n\le 500$

$100\%:1\le m\le n-1, 2\le n\le 10^5, |a_i|\le 10^5$