Best stretch of k days

Problem

You have the daily profit of n days. Choose k consecutive days so that their total profit is as large as possible, and print that total. Profits can be negative.

Input, output and limits

Input: Line 1: the integers n and k. Line 2: n integers, the profits.
Output: One integer: the largest total of k consecutive days.
Constraints: 1 ≤ k ≤ n ≤ 2 * 10^5
-10^9 ≤ profit ≤ 10^9

Examples

Example

Input

6 3
2 1 5 1 3 2

Output

The windows total 8, 7, 9 and 6. The best is 9.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Adding k values for every window costs about n x k steps, which is too slow.

Hint 2

Move the window by one day: add the new day and subtract the day that left.

Hint 3

Start the best total from the first window, not from 0, because all totals can be negative.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More How to Approach a Problem problems

Problem

Input, output and limits

Examples

Hints

More How to Approach a Problem problems