Maximum Subarray of Size at Least K

Choose a non-empty contiguous subarray of length at least K that maximizes the sum of its elements. The catalog's second example answer of −5 is wrong; [-2,1] has the larger sum −1.

This site uses a standard input/output protocol.

输入格式

The first line contains N K, and the second line contains N integers. This site uses 1≤K≤N≤100000 and elements in −10⁹..10⁹.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 2
10 -2 5

输出：

13

样例 2

输入：

5 2
-3 -2 1 -6 -30

输出：

-1

样例 3

输入：

3 1
-8 -2 -7

输出：

-2

样例说明

Example 1: choose three elements, for a total of 13. Example 2: choose −2, 1, for a total of −1, correcting the source example's −5. Example 3: choose the single element −2; an empty array is not allowed.