Blob's Apple Pies

Interview

Time limit1sMemory limit1024 MB

Summary

Given N positive integers arranged in a circle, find the maximum sum of K consecutive values, where the block may wrap around the end.

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

Problem

Blob is hungry again today. So Blob went to the chef Yeonwoo and asked for something delicious.

Yeonwoo wanted to give the cute Blob the tastiest food possible, so Yeonwoo decided to make apple pie, the dish Yeonwoo makes best. Yeonwoo baked $N$ apple pies and arranged them on a table in a circle.

Each apple pie is represented by a positive integer, which denotes how tasty it is. (A larger number means a tastier apple pie.)

Blob wants to eat $K$ of the $N$ apple pies. Since Blob wants to eat without putting in any effort, Blob will eat $K$ apple pies that are placed consecutively.

Help Blob and find the maximum possible sum of the tastiness of the apple pies Blob will eat!

Input

The first line gives the number of apple pies and the number of apple pies Blob will eat, $N$ and $K$ , separated by a space.

The second line gives $A_1, A_2, \cdots, A_N$ , the values denoting the tastiness of the apple pies, separated by spaces.

Output

Print the maximum possible sum of the tastiness of the apple pies Blob will eat.

Constraints

$1 \le K \le N \le 10^5$
$1 \le A_i \le 100$ $(1 \le i \le N)$

Examples1

Example 1
Input
```
4 2
5 2 3 4
```
Expected output
```
9
```