题目描述

有 $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 是能达到的最大力量。

数据范围

$10\%:n\le 8$

$20\%:n\le 1000$

对于额外的 $10\%:$ 所有 $a_i$ 相等

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