Description

Hardworking JYY planted a lot of carrots in his garden. But this morning, JYY found that a large group of rabbits from the Kingdom of JSOI had occupied his entire garden. The rabbits ate all the carrots—how will JYY survive the winter? Unable to tolerate it anymore, JYY decided to take out his powerful hunting rifle to eliminate these rabbits.

JYY's garden is a circular ring formed by connecting $n$ small vegetable plots in order, numbered from $1$ to $n$. Plot $i$ and plot $i+1$ are adjacent. Since the garden is circular, plot $1$ and plot $n$ are also adjacent.

Now, plot $i$ has $r_i$ rabbits. JYY's rifle has $k$ bullets. Each time, JYY can choose one plot and fire one shot, and all rabbits on that plot will be eliminated. However, because the rifle is too powerful, it will scare the rabbits on adjacent plots. So, if JYY fires at plot $i$, then the rabbits on plot $i+1$ will run to plot $i+2$. Similarly, the rabbits on plot $i-1$ will run to plot $i-2$. JYY wants to know how to use these $k$ bullets to eliminate as many rabbits as possible.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers, where the $i$-th integer is $r_i$.

Output Format

Output one integer in one line, representing the maximum number of rabbits JYY can eliminate.

5 2
6 1 5 3 4

13

Hint

Sample Explanation

First, fire at plot $1$, which becomes $0\ 0\ 6\ 7\ 0$. Then fire at plot $4$. It can be proven that there is no answer greater than $13$.

Constraints

For $100\%$ of the testdata, $3\leq n\leq 4000$, $0\leq k\leq 4000$, $r_i\leq 10^5$.

Translated by ChatGPT 5