Problem Description

On a desk, there are $ N $ candies arranged in a single row, numbered from $ 1 $ to $ N $ from left to right. The deliciousness of candy $ i $ ($1 \leq i \leq N$) is $ A_i $.

JOI wants to eat some of these $ N $ candies.

However, to avoid eating too many candies, for any consecutive $ K $ candies, he will eat at most $ 2 $ of them. That is, for any $ j $ ($1 \leq j \leq N - K + 1$), the number of candies he eats among the $ K $ consecutive candies from candy $ j $ to candy $ j + K - 1 $ must be at most $ 2 $.

Under these conditions, JOI wants to maximize the total deliciousness of the candies he eats.

Given the deliciousness of $ N $ candies and $ K $, write a program to find the maximum total deliciousness of the candies JOI can eat.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $

Output Format

Output to the standard output the maximum total deliciousness of the candies JOI can eat in one line.

Sample Input and Output

Sample Input #1

5 4
1 3 2 4 3

Sample Output #1

8

Sample Input #2

6 3
3 7 1 5 6 4

Sample Output #2

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

Notes/Hints

Constraints

• $2 \leq K \leq N \leq 3,000$.
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).
• All input values are integers.

Subtasks

1. ($ 4 $ points) $N \leq 20$.
2. ($ 19 $ points) $K \leq 10$.
3. ($ 47 $ points) $N \leq 300$.
4. ($ 30 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judging system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked from the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

When JOI eats candies $ 1 $, $ 4 $, and $ 5 $, the total deliciousness is $ 8 $. There is no way to eat candies such that the total deliciousness is $ 9 $ or more while ensuring that no more than $ 2 $ candies are eaten in any consecutive group of $ 4 $ candies. Therefore, output $ 8 $. This input example satisfies the constraints of all subtasks.

Sample Explanation 2

When JOI eats candies $ 1 $, $ 2 $, $ 4 $, and $ 5 $, the total deliciousness is $ 21 $. There is no way to eat candies such that the total deliciousness is $ 22 $ or more while ensuring that no more than $ 2 $ candies are eaten in any consecutive group of $ 3 $ candies. Therefore, output $ 21 $. This input example satisfies the constraints of all subtasks.

Sample Explanation 3

This input example satisfies the constraints of all subtasks.

Sample Explanation 4

This input example satisfies the constraints of all subtasks.

见题面 Input 部分

见题面 Output 部分