Picking Numbers on a Circle

Time limit1sMemory limit512 MB

Summary

Pick exactly K numbers from a circle of N values so that no two chosen are adjacent, maximizing the sum.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Heap, Linked list
Solved: No attempts yet

Problem

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.

Input

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}$ .

Output

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

Examples5

Example 1
Input
```
10 4
2 1 3 1 2 1 3 1 3 1
```
Expected output
```
11
```
Example 2
Input
```
3 1
5 9 7
```
Expected output
```
9
```
Example 3
Input
```
4 2
1 100 1 100
```
Expected output
```
200
```
Example 4
Input
```
6 2
5 6 5 1 1 1
```
Expected output
```
10
```
Example 5
Input
```
6 2
10 1 1 1 1 10
```
Expected output
```
11
```