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

题目描述

程老师在学校院子里有一片花坛，绕着那棵老樟树围了整整一圈，首尾相接，连成一个环形。花坛里的土常年松着，盆与盆挨得很紧，绕着树干正好围成完整的一圈。这一圈里一共摆了 $n$ 盆花，沿着顺时针方向一盆挨一盆地编上号：$1$ 号、$2$ 号，一直到 $n$ 号。因为花带是环形的，编到 $n$ 号之后再往前，就又回到了 $1$ 号，中间没有断口。换句话说，$1$ 号花和 $n$ 号花是挨着的两盆，它们之间隔着的距离，跟其他任意两盆相邻花之间隔的完全一样。

每盆花旁边都插着一块小木牌，上面写着这盆花的观赏值 $v_i$。程老师估观赏值的标准很直白：花开得旺、花期又长的，观赏值是个正数，数字越大越值得摆上展台；也有几盆花已经蔫了，花垂着、叶子也黄了，但搬走枯枝败叶同样算整理花坛，只是要搭上功夫，程老师索性把这种花的观赏值记成负数。每块小木牌上的数是程老师事先定好的，摘花之前不会再变。所以牌上的数有可能是正的，有可能是负的，也有可能是 $0$，正负大小都没有什么规律。

学校展厅要办一场花艺展，程老师打算从花坛里摘走一些花布置展台。他给自己定下两条规矩。第一条关于花坛：相邻的两盆花不能都摘——摘了某一盆，它左右两边各一盆就得留着不动；再往外隔一盆，就不受这条规矩约束了。第二条关于展厅：展台的位置有限，摘走的花一共至多 $p$ 盆，少摘一些可以，觉得这一季没什么好摘的，一盆都不摘、空着手回去也可以。摘下来的每一盆，都按它木牌上的数算进总观赏值，把这些数加起来，就是这次布展的观赏值总和。总和可能是正数，也可能因为顺手摘了蔫花变成负数；但他要是选择一盆都不摘，总和就一定是 $0$。

程老师想知道，按这两条规矩，他能获得的最大观赏值总和是多少。请你帮他算出来。

输入格式

从文件 garden.in 中读入数据。

第一行两个整数 $n$、$p$，表示花坛里花的盆数与摘花盆数的上限。

第二行 $n$ 个整数 $v_1, v_2, \dots, v_n$，依次表示第 $1$ 盆到第 $n$ 盆花的观赏值。

输出格式

输出到文件 garden.out 中。

一行一个整数，表示最大观赏值总和。

数据范围

特殊性质 A：保证 $p \ge \lfloor n/2 \rfloor$。

特殊性质 B：保证 $v_1$ 与 $v_n$ 均为负数。

对于所有测试点：$1 \le n \le 500$，$1 \le p \le n$，$|v_i| \le 10^6$。

样例

6 2
8 -1 3 -1 3 7

11

6 2
9 1 8 1 8 9

17

4 3
5 -1 5 -1

10

样例解释

样例 2：摘第 $1$ 盆和第 $3$ 盆，观赏值总和是 $9 + 8 = 17$（摘第 $1$ 盆和第 $5$ 盆、第 $3$ 盆和第 $6$ 盆也一样）。摘第 $1$ 盆和第 $6$ 盆看似有 $9 + 9 = 18$，但这两盆在环形花带上相邻，不能都摘；摘第 $1$、$3$、$5$ 盆共 $9 + 8 + 8 = 25$，又超过了两盆的上限。