Two Stores

A business is about to open two stores on a large commercial street. The street consists of N squares arranged in a row. Each store will cover K consecutive squares, and the two stores can overlap.

The business knows that each square i (where 1 ~\le~ i ~\le~ N) is expected to yield a profit ~\mathbf{A_i}~ if covered by any store - even if covered by both stores, the total profit it yields remains ~\mathbf{A_i}~.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the values of N, K, and ~\mathbf{A_i}~, calculates the maximum profit the business can have by opening two stores on the commercial street, each covering K consecutive squares.

Input Files

The input files named shops.in are text files with the following structure. The first line contains two integers N and K, separated by a space. The second line contains N integers ~\mathbf{A_i}~ (for 1 ~\le~ i ~\le~ N) separated by a space: the i-th number represents the expected profit from the i-th square.

Output Files

The output files named shops.out are text files consisting of a single line with a single integer: the maximum profit the business can have by opening two stores, each covering K consecutive squares.

Examples of Input - Output Files:

1o

STDIN (shops.in)

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

STDOUT (shops.out)

71

2o

STDIN (shops.in)

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

STDOUT (shops.out)

90

Explanation:

In the first example, we can place the first store to have a profit of 15+12+10 and the second store in a way to have a profit of 20+4+10. In the second example, we can arrange them so that the first store has a profit of 5+20+20 and the second store has a profit of 20+15+10.

Constraints:

• 3 ~\le~ N ~\le~ 2.000.000,
• 1 ~\le~ K ~\le~ N2,
• 1 ~\le~ ~\mathbf{A_i}~ ~\le~ 1.000.000,
• The sum of all the ~\mathbf{A_i}~ will not exceed 1.000.000.000.
• Maximum execution time: 1sec.
• Maximum available memory: 64MB.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: shops *)

for PASCAL coders

/* USER: username
LANG: C
TASK: shops */

for C coders

/* USER: username
LANG: C++
TASK: shops */

for C++ coders

/* USER: username
LANG: Java
TASK: shops */

for Java coders

# USER: username
# LANG: Python
# TASK: shops

for Python coders