Description

You are given an integer sequence $\{A_1, A_2, \cdots, A_n\}$ of length $n$. Your task is to find a non-empty contiguous subsequence with a length not exceeding $m$ such that the sum of this subsequence is maximized.

Input Format

The first line contains two integers $n$ and $m$;

The second line contains $n$ integers separated by spaces, where the absolute value of each number is less than $1000$.

Output Format

Output a single integer representing the maximum sum of a non-empty contiguous subsequence with length not exceeding $m$.

Sample 1

6 4
1 -3 5 1 -2 3

7

Constraints & Hints

For $50\%$ of the test cases, $1 \le n, m \le 10^4$;

For $100\%$ of the test cases, $1 \le n, m \le 2 \times 10^5$.