该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，以及一个整数 $k$。从序列中选择 $k$ 个非空子段，使得任意相邻子段之间至少间隔 1 个元素（即两个子段在原序列中的区间不交且至少隔 1 个索引）。求选中子段的元素和总和最大值。

输入格式

$n,k$
$a_1,a_2 \dots a_n$

输出格式

输出一个整数，表示最大总和。

数据范围

• $1 \le n \le 1 \times 10^5$
• $1 \le k \le \min\left(\left\lfloor\dfrac{n}{2}\right\rfloor, 100\right)$
• $-10^9 \le a_i \le 10^9$

样例

输入

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

输出

16

解释：可选择子段 $[3,6]$ 和 $[8,8]$，分别得到 $5+2=7$ 与 $4-2+6=8$，总和为 $16$。