One-Dimensional Scrabble

Two friends, Maria and John, are playing a variation of the well-known game Scrabble. This game generally aims at forming words and placing them on a two-dimensional board so that each player maximizes the points they get from each word.

However, the variation that the two friends are playing has the following simple rules:

• The board where the words are placed is one-dimensional and consists of N squares, each of which can hold one letter.
• The players simultaneously place two words on the board, each word having a length of exactly K letters. These words cannot overlap, but they can touch.
• The points earned for each word depend not on the letters in the word but on the position on the board where the word is placed. Each square of the board has a designated point value based on the points a player earns by placing a word there.

For example, suppose the board has N=10 squares, initially empty, and the point values for each square are as follows:

Maria has formed two words with a length of K=3 letters each: "ΝΑΙ" and "ΟΧΙ". Now she needs to place them on the board to maximize her points. She can achieve this by placing them as follows:

In this way, she earns 15+12+10=37 points for the first word and 20+4+10=34 points for the second word, resulting in a total of 37+34=71 points.

Can you help Maria place the first two words to maximize her points?

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that, after reading the values of N and K and the points corresponding to each square of the board, prints the maximum number of points Maria can earn by playing first and placing the two words appropriately.

Input Files:

The input files named scrabble1d.in are text files with the following structure. They contain exactly two lines. The first line contains two integers N (3 ~\le~ N ~\le~ 2.000.000) and K (1 ~\le~ K ~\le~ N/2), separated by a single space: the size of the board and the length of each word. The second line contains exactly N integers P~\mathbf{_i}~ separated between them by a single space (1 ~\le~ P~_i~ ~\le~ 1.000.000, where 1 ~\le~ i ~\le~ N). The integer P~_i~ represents the points corresponding to the ~i~-th square of the board. You can assume that the sum of all ~P_i~ values does not exceed ~1.000.000.000~.

Output Files:

The output files named scrabble1d.out are text files with the following structure. They have exactly one line containing exactly one integer: the maximum number of points Maria can earn by placing the words.

Examples of Input - Output Files:

1o

STDIN (scrabbled.in)

10 3
2 4 15 12 10 1 1 20 4 10

STDOUT (scrabbled.out)

71

Explanation: This is exactly the example from the previous page.

2o

STDIN (scrabbled.in)

10 3
1 5 20 20 20 15 10 1 1 1

STDOUT (scrabbled.out)

90

Explanation: Note that in this case, it is advantageous for Maria to place her words consecutively. Therefore, (5+20+20)+(20+15+10)=90.