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

附加文件

题目描述

同学们来到操场上种树。

操场是圆形的，同学们沿着操场外侧挖了 n 个树坑。假设树坑编号为 1 ~ n，则 1 号和 2 号相邻，2 号和 3 号相邻，……，n-1 号和 n 号相邻，n 号和 1 号相邻。

另外，每个树坑里如果种树，会产生一个观赏度。编号为 i 的树坑里种树所产生的观赏度为 Ai。Ai 可能为负数。

但是现在只有 k 棵树苗。该如何种植这些树苗呢？

这时，信竞队长提出了一些要求：

1、要把所有树苗全部种上。

2、一个树坑最多只能种一棵树苗。

3、任意两个相邻的树坑不能同时种上树苗。

在满足以上要求的条件下，信竞队长想要知道，如何种树可以使得产生的观赏度之和最大。

你能帮助信竞队长吗？你只需要输出这个最大值。

如果没有合法的种树方案，则输出 “No solution!” （输出引号里的内容，引号不输出）。

输入格式

第一行：n, k

第二行，n 个整数 Ai

输出格式

一行，表示答案

样例输入1

7 3
1 2 3 4 5 6 7

样例输出1

15

样例输入2

7 4
1 2 3 4 5 6 7

样例输出2

No solution!

数据规模

100% 的数据：k ≤ n ≤ 200,000；|Ai| ≤ 1000

具体如下：