题目描述

给定一个长度为 $n$ 的环状数列 $a_1,a_2,\cdots, a_n$，请从中挑选出 $k$ 个数，构成独立集，且数字之和达到最大。

所谓环状，是指在考虑相邻关系时，需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。所谓独立集，就是挑选出的数字在原来的圆环上不能相邻。

输入格式

第一行：两个整数表示 $n$ 与 $k$。 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

单个整数：表示 $k$ 个独立的数字之和的最大值。

6 2
1 2 3 4 5 6

10

样例解释 1

6+4=10

5 2
1 3 4 3 1

6

样例解释 2

这个例子说明，最大数不一定在最大独立集里。

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq 20$；
• 对于 $60\%$ 的数据，$2\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$2\leq n\leq 500,000$，
• $1\leq k\leq n/2$
• $1\leq a_i\leq 1,000,000$。