P7240 [JSOI2014] Shooting Rabbits

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.

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

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

### 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