题目描述

Goneril 是一头严重睡眠不足的奶牛。她的一天被划分为 $N$（$3 \leq N \leq 3,830$）个等长的时间段，但她只能在其中的 $B$（$2 \leq B < N$）个时间段里睡觉（这些时间段不一定是连续的）。由于她的荷尔蒙水平影响，每个时间段都有一个固定的效用值 $U_i$（$0 \leq U_i \leq 200,000$），表示在该时间段睡觉能获得的休息量。这些效用值是固定的，不受 Goneril 的选择影响，包括她是否决定在该时间段睡觉。

借助闹钟，她可以精确选择哪些时间段睡觉，哪些时间段做更重要的事情（比如写论文或看棒球比赛）。然而，她只能在时间段的边界处上床或起床。

她的目标是选择睡觉的时间段，使得这些时间段的效用值之和最大化。但有一个限制：每次她上床睡觉时，第一个时间段的效用值为 0（因为她需要时间入睡）。

此外，时间段是环形排列的。也就是说，如果 Goneril 在第 $N$ 个和第 $1$ 个时间段都在睡觉，那么第 $1$ 个时间段的效用值仍然可以正常计算（前提是她在第 $1$ 个时间段之前已经入睡）。

请问 Goneril 能获得的最大总睡眠效用是多少？

输入格式

• 第 1 行：两个空格分隔的整数 $N$ 和 $B$。
• 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数 $U_i$，表示第 $i$ 个时间段的效用值（$0 \leq U_i \leq 200,000$）。

输出格式

• 一行，一个整数，表示 Goneril 能获得的最大总睡眠效用。

示例输入 1

5 3
2
0
3
1
4

示例输出 1

6

提示

输入解释：
一天被划分为 5 个时间段，效用值依次为 2, 0, 3, 1, 4。Goneril 必须选择 3 个时间段睡觉。

输出解释：
Goneril 可以选择在第 4、5 和 1 个时间段睡觉。此时：

• 第 4 个时间段（上床睡觉，效用为 0）。
• 第 5 个时间段（正常睡觉，效用为 4）。
• 第 1 个时间段（正常睡觉，效用为 2）。
  总效用为 $0 + 4 + 2 = 6$。

题目来源

USACO 2005 January Gold