Maximizing Sleep Utility

Betsy the cow has her day divided into $N$ segments ($3 \le N \le 3830$) in a cyclic manner, and she must sleep during exactly $B$ segments ($2 \le B < N$). Each segment $i$ has an associated utility value $U_i$ ($0 \le U_i \le 2 \times 10^5$). However, when she sleeps, only the segments after the first one in each contiguous sleep period produce utility, because the first segment of each sleep period (the moment she falls asleep) does not count. With the help of an alarm clock, Betsy can start sleeping at any segment boundary, but she must wake up at another boundary. Note that the time is cyclic; for example, if she starts sleeping at segment $N$ and continues into segment $1$, then segment $1$'s utility will be counted (and segment $N$’s utility will be lost as it is the start of that sleep period).

In other words, Betsy will select exactly $B$ segments to sleep, which will form one or more contiguous intervals on a circle. For each contiguous block of sleep of length $L\ge1$, the utility gained is the sum of utilities of all segments except the first one. Betsy wants to maximize the total sleep utility. It turns out that the optimal solution is to choose one contiguous block of $B$ segments (taken cyclically) so that only a single segment (the first one) is penalized.

Formally, if Betsy chooses a contiguous block of $B$ segments, say $x_0, x_1, \dots, x_{B-1}$ (in cyclic order), the total utility is given by: [ \text{Utility} = \left(\sum_{i=0}^{B-1} x_i\right) - x_0. ] Your task is to compute the maximum possible total sleep utility Betsy can achieve by selecting the optimal contiguous block of $B$ segments from the circular list.

inputFormat

The input consists of two lines:

N B
U1 U2 ... UN

Here, the first line contains two integers  N  and  B  as described above, and the second line contains N integers representing the utility values of the time segments.

outputFormat

Output a single integer, the maximum total sleep utility that can be achieved.

sample

3 2
5 1 5

5