Maximum Sum

Interview

Time limit1sMemory limit128 MB

Summary

Given n integers and a window size k, find the largest sum of any k consecutive terms.

Level: Easy3 of 10
Topics: Array, Sliding window, Prefix sum
Solved: No attempts yet

Problem

You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ and a positive integer $k$ ( $1 \le k \le n$ ). Write a program that outputs the maximum value of the sum of $k$ consecutive terms

$S_i = a_i + a_{i+1} + \cdots + a_{i+k-1} \quad (1 \le i \le n-k+1).$

Input

The first line contains a positive integer $n$ ( $1 \le n \le 100000$ ) and a positive integer $k$ ( $1 \le k \le n$ ) in this order, separated by a space. Each of the following lines holds one term of the sequence: line $1 + i$ (for $1 \le i \le n$ ) contains $a_i$ ( $-10000 \le a_i \le 10000$ ).

Output

Print a single line containing only the maximum value of $S_i$ .

Examples1

Example 1
Input
```
5 3
2
5
-4
10
3
```
Expected output
```
11
```