Maximum Hopscotch Earnings

The game is played on a line of squares numbered from 1 to \(N\) (with \(3\le N\le 250000\)). Each square \(i\) has an integer monetary value \(V_i\) (where \(-2\times10^9\le V_i\le2\times10^9\)). The cow starts at square 0 (which has no value) and makes a (possibly empty) sequence of jumps toward square \(N\). On the outbound trip, if the cow is currently on square \(i\), she may jump to any square \(j\) satisfying \[ 1\le j-i\le K \quad (2\le K\le N),\quad j\le N. \]

At any time the cow may decide to turn around and jump back toward square 0. However, during the return trip the following extra restrictions apply:

• The cow is not allowed to land on any square that was visited during the outbound trip (except for square 0).
• With the exception of square 0, every square she lands on in the return trip must be exactly the immediate predecessor of some square that was visited on the outbound trip. In other words, if a square \(a\) was visited on the outbound leg, then square \(a-1\) may be used as a landing point on the return leg.

The final score is the sum of the monetary values of all squares landed on (both outbound and return). Your task is to compute the maximum cash that can be earned.

inputFormat

The first line contains two integers \(N\) and \(K\). The second line contains \(N\) integers \(V_1, V_2, \dots, V_N\) representing the monetary values of squares 1 through \(N\).

outputFormat

Output a single integer representing the maximum cash the cow can earn.

sample

6 3
0 1 2 -3 4 5

12