时间限制：1秒　　内存限制：256M

---

【问题描述】

　　我们来玩一个游戏：\(n\) 个整数顺时针围成一圈：\(a[1],a[2],…,a[n]\)，其中 \(a[1]\) 和 \(a[n]\) 相邻。你可以从中取走 \(k\) 个数，但是相邻的两个不可以同时取走。请你计算取得数和的最大值。

【输入格式】

　　第 \(1\) 行一个整数 \(n\)，接下来的一行有 \(n\) 个自然数 \(a_i\)。

【输出格式】

　　输出一个整数，表示取得数之和的最大值。

【输入输出样例】

　Input

10 4 
90 100 -100 1 1 -3 -60 5 7 -30

　Output

105

【数据限制】

　　对于 \(20\%\) 的数据满足：\(n≤20\)
　　对于 \(60\%\) 的数据满足：\(n≤6000\)
　　对于 \(100\%\) 的数据满足：\(n≤500000,1≤k≤n/2,-10^6<=Ai<=10^6\)

【来源】

　　Mr.he