Candies 2

Problem Statement

There are N candies arranged in a single row on a table, numbered from 1 to N from left to right. The deliciousness of candy i (1 ≦ i ≦ N) is A_i.

JOI-kun decided to choose some of the N candies to eat.

However, to avoid eating too many candies, for any consecutive K candies, he must eat at most 2 of them. In other words, for every j (1 ≦ j ≦ N - K + 1), the number of candies eaten among the consecutive K candies from candy j to candy j + K - 1 must be at most 2.

Under this condition, JOI-kun wants to maximize the total deliciousness of the candies he eats.

Given the deliciousness of the N candies and K, write a program to find the maximum possible total deliciousness of the candies JOI-kun eats.

Constraints

• 2 ≦ K ≦ N ≦ 3 000.
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N).
• All input values are integers.

Input

The input is given from standard input in the following format.
N K
A₁ A₂ … A_N

Output

Output the maximum possible total deliciousness of the candies JOI-kun eats in one line to standard output.

Sample Input and Output

Sample Input 1

5 4
1 3 2 4 3

Sample Output 1

8

If JOI-kun eats candy 1, candy 4, and candy 5, the total deliciousness is 8.

Among all ways of eating such that the number of candies eaten in any consecutive 4 candies is at most 2, there is no way with a total deliciousness of 9 or more. Therefore, output 8.

Sample Input 2

6 3
3 7 1 5 6 4

Sample Output 2

21

If JOI-kun eats candy 1, candy 2, candy 4, and candy 5, the total deliciousness is 21.

Among all ways of eating such that the number of candies eaten in any consecutive 3 candies is at most 2, there is no way with a total deliciousness of 22 or more. Therefore, output 21.

Sample Input 3

5 2
3 3 2 2 1

Sample Output 3

11

Sample Input 4

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

Sample Output 4

4427122428

---