题目描述

在某个星球上，一天由 $N$ 个小时构成，我们称 $0$ 点到 $1$ 点为第 $1$ 个小时、$1$ 点到 $2$ 点为第 $2$ 个小时，以此类推。

在第 $i$ 个小时睡觉能够恢复 $U_i$ 点体力。

在这个星球上住着一头牛，它每天要休息 $B$ 个小时。

它休息的这 $B$ 个小时不一定连续，可以分成若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。

为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。

另外，因为时间是连续的，即每一天的第 $N$ 个小时和下一天的第 $1$ 个小时是相连的（$N$ 点等于 $0$ 点），这头牛只需要在每 $N$ 个小时内休息够 $B$ 个小时就可以了。

请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。

输入格式

第 $1$ 行输入两个空格隔开的整数 $N$ 和 $B$。

第 $2$ 到 $N+1$ 行，第 $i+1$ 行包含一个整数 $U_i$。

输出格式

输出一个整数，表示恢复的体力值。

样例

输入样例：

5 3
2
0
3
1
4

输出样例：

6

样例解释

$N=5, B=3$

恢复体力值：$U = [2,0,3,1,4]$

需要选 $B=3$ 个小时睡觉，但每段睡眠的第一个小时不恢复体力。

因为时间是环形的（第5小时与第1小时相连），所以可以跨越边界选择睡眠区间。

一种最优方案：在第 4、5、1 小时睡觉（注意这是环形连续的）。

• 第 4 小时：睡眠第一小时，不恢复体力 → 0
• 第 5 小时：恢复体力 4
• 第 1 小时：恢复体力 2 总恢复体力 $0+4+2=6$。

也可以在第 3、4、5 小时睡觉：

• 第 3 小时：睡眠第一小时，不恢复体力 → 0
• 第 4 小时：恢复 1
• 第 5 小时：恢复 4 总和 5，不如 6。

所以最大为 6。

数据范围

• $3 \le N \le 3830$
• $2 \le B < N$
• $0 \le U_i \le 200000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB