Signal Tower Range

Signal Tower Range

A relay line has n signal towers in a row. Tower i has a signal strength a[i] (which may be negative — a jammed ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​​‌​​​‌‌‌​​​​‌‌​​​​‌​​‌‌​​‌​​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​‌​​​​‌‌​​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌​​​‌​​‌‌​​‌​​​‌‌​​​​​​‌‌‌​​‌tower actively cancels nearby signal).

You must choose a contiguous range of towers, with length between 1 and k (inclusive), to activate as a relay segment. Maximize the total signal strength of the chosen segment.

Input

Line 1: two integers n k (1 ≤ k ≤ n ≤ 2·10^5) Line 2: n integers a_1 … a_n (-10^9 ≤ a_i ≤ 10^9) ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​​‌​​​‌‌‌​​​​‌‌​​​​‌​​‌‌​​‌​​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​‌​​​​‌‌​​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌​​​‌​​‌‌​​‌​​​‌‌​​​​​​‌‌‌​​‌

Output

A single integer: the maximum possible sum of a contiguous segment whose length is at most k.

Example

Input:

5 2
3 -1 4 -2 5

Output:

5

Explanation: every window of length ≤2 is checked — [3,-1]=2, [-1,4]=3, [4,-2]=2, [-2,5]=3, and each single element on its own. The best is the ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​​‌​​​‌‌‌​​​​‌‌​​​​‌​​‌‌​​‌​​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​‌​​​​‌‌​​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌​​​‌​​‌‌​​‌​​​‌‌​​​​​​‌‌‌​​‌single tower a[5]=5.

Constraints

• 1 ≤ k ≤ n ≤ 2·10^5
• -10^9 ≤ a_i ≤ 10^9
• The answer fits in a signed 64-bit integer. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​​‌​​​‌‌‌​​​​‌‌​​​​‌​​‌‌​​‌​​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​‌​​​​‌‌​​​​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌​​​‌​​‌‌​​‌​​​‌‌​​​​​​‌‌‌​​‌

5 2
3 -1 4 -2 5

5

6 3
-2 1 -3 4 -1 2

5