题目描述

$n$ 个位置围成一个环，第 $i$ 个位置的价值为 $a_i$。你需要恰好选择其中 $c$ 个位置。

对于每个被选择的位置 $i$，如果它在环上的前一个位置也被选择，则获得 $a_i$ 分；否则这个位置不产生得分。位置 $1$ 的前一个位置是位置 $n$。

请计算能够得到的最大总分。

输入格式

第一行包含两个整数 $n$ 和 $c$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

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

5 3
4 2 7 1 6

11

数据范围与提示

• $1 \le c \le n \le 4000$
• $0 \le a_i \le 10^6$