Circular Sequence
Description
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:
- The circular distance between any two elements of the subsequence, in their original position in $A$, should be at least $D + 1$.
- The sum of all numbers in the subsequence should be as large as possible.
The first line of input contains two integers $N$ and $D$ ($1 \le N \le 100\,000$, $0 \le D < 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 a single integer: the sum of all numbers in the required subsequence.
Input
The first line of input contains two integers $N$ and $D$ ($1 \le N \le 100\,000$, $0 \le D < 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.
6 2
1 5 3 2 6 1
4 1
2 1 1 2
11
3