Weather Intern's Temperature Sum

Interview

Time limit1sMemory limit128 MB

Summary

Given N daily temperatures, find the maximum sum over any contiguous window of exactly K days.

Level: Easy2 of 10
Topics: Sliding window, Array
Solved: No attempts yet

Problem

Hyunsoo measured an integer temperature every day for N days. From this sequence, choose a contiguous period of exactly K days and compute the sum of its temperatures.

Find the maximum possible sum among all contiguous K-day periods.

Input

The first line contains two integers N and K separated by a space. N is the total number of days with temperature measurements, and satisfies 2 <= N <= 100. K is the number of consecutive days to sum, and satisfies 1 <= K <= N.

The second line contains N integers separated by spaces, where each integer is the temperature measured on that day. Each temperature is between -100 and 100, inclusive.

Output

Print the maximum sum of temperatures over any contiguous K-day period.

Examples1

Example 1
Input
```
10 2
3 -2 -4 -9 0 3 7 13 8 -3
```
Expected output
```
21
```