Problem Description

Bessie is a very sleep-deprived cow. Her day is evenly divided into $N$ time segments ($3 \leq N \leq 3830$), and she wants to sleep for $B$ of them ($2 \leq B \lt N$). Each segment has a utility value $U_i$ ($0 \leq U_i \leq 2 \times 10^5$), which only counts when she is sleeping.

With the help of an alarm clock, Bessie can choose to fall asleep at any time. Of course, she can only fall asleep and wake up at the boundaries between segments.

Bessie wants to maximize the total utility gained during sleep. Unfortunately, the first segment of each sleep period is the “falling asleep” segment and does not contribute any utility.

The time segments form a cycle (days repeat). If Bessie sleeps across time $N$ and time $1$, then she will gain the utility value of time $1$.

Input Format

The first line contains two integers $N, B$.

The next $N$ lines each contain one integer, representing the utility value of the $i$-th time segment.

Output Format

Output the maximum total utility.

5 3
2
0
3
1
4

6

Hint

Fall asleep starting from the $4$-th time segment, and wake up at the end of the $1$-st time segment.

Translated by ChatGPT 5