D. Circular Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A circular sequence of $$$N$$$ elements is a sequence arranged in a circle such that elements $$$1$$$ and $$$2$$$, $$$2$$$ and $$$3$$$, ..., $$$N - 1$$$ and $$$N$$$, $$$N$$$ and $$$1$$$ are adjacent. The circular distance between two elements $$$i$$$ and $$$j$$$ of the sequence is the minimal number of moves between adjacent elements to get from $$$i$$$ to $$$j$$$.

You are given a circular sequence $$$A$$$ of $$$N$$$ integers. Your task is to select a subsequence of $$$A$$$ that satisfies the following conditions:

  1. The circular distance between any two elements of the subsequence, in their original position in $$$A$$$, should be at least $$$D + 1$$$.
  2. The sum of all numbers in the subsequence should be as large as possible.
Input

The first line of input contains two integers $$$N$$$ and $$$D$$$ ($$$1 \le N \le 100\,000$$$, $$$0 \le D \lt N$$$). The second line contains the elements of the circular sequence $$$A$$$ separated by spaces. The elements are integers ranging from $$$1$$$ to $$$10^9$$$.

Output

Output a single integer: the sum of all numbers in the required subsequence.

Examples
Input
6 2
1 5 3 2 6 1
Output
11
Input
4 1
2 1 1 2
Output
3