Picking Numbers on a Circle

kcm1700 gave ntopia the following task. $N$ numbers are placed around a circle. Pick $K$ of them so that no two picked numbers are neighbors, and make the sum of the picked numbers as large as possible. Picking neighbors means that among the picked numbers there are two that sit next to each other on the circle.

The numbers form a circle, so the first number and the last number are neighbors too. Write a program that computes the largest sum you can get by picking $K$ numbers with no two of them adjacent.

The first line contains a positive integer $N$ ($3 \le N \le 10^6$) and an integer $K$ ($1 \le K \le N/2$), separated by a space.

The second line contains the $N$ natural numbers of the circle in clockwise order, separated by spaces. Each number is smaller than $2^{31}$.

Print the maximum sum on the first line. The answer is smaller than $2^{31}$.