Search for the maximum sum of a subarray with a length constraint

Go Hard loops

Task «Search for the maximum sum of a subarray with a length constraint»

Given an array of integers (positive and negative). It is necessary to find the maximum sum of a contiguous subarray whose length does not exceed a given number K. If there are several such subarrays, output the first one in order (with the smallest starting index). If the array is empty or K=0, output 0.

Input Format

The first line contains two integers N (1 ≤ N ≤ 10^5) and K (0 ≤ K ≤ N). The second line contains N integers separated by spaces.

Output Format

One integer — the maximum sum of a subarray of length no more than K.

Examples

Example 1

INPUT

5 2
-1 -2 -3 -4 -5

OUTPUT

-1

Example 2

INPUT

4 0
1 2 3 4

OUTPUT

0

main.go