Hardworking JYY has planted many carrots in his garden! However, this morning, JYY discovered that a large group of rabbits from the JSOI Kingdom had occupied his entire garden! The rabbits ate all the carrots, and now JYY has nothing to survive the winter! Unable to bear it any longer, JYY decided to take out his powerful shotgun to eliminate these rabbits.

JYY's garden is a ring formed by $N$ small plots of land connected in sequence. The plots are 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. Currently, there are $R_i$ rabbits on plot $i$.

JYY has $K$ bullets. Each time, JYY can choose one plot to shoot at, and all the rabbits on that plot will be eliminated.

However, because JYY's shotgun is too powerful, it will scare the rabbits on the adjacent plots. Therefore, if JYY shoots at plot $i$, the rabbits on plot $i+1$ will run to plot $i+2$, and 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

The first line contains two integers $N$ and $K$. The next line contains $N$ integers, where the $i$-th integer is $R_i$.

Output

Output a single integer representing the maximum number of rabbits JYY can eliminate.

Constraints

• For 20% of the data: $N \le 10$
• For 40% of the data: $N \le 100$
• For 70% of the data: $N \le 1000$
• For 100% of the data: $3 \le N \le 4000$, $0 \le K \le 4000$, $0 \le R_i \le 10^5$

Examples

Input 1

5 2
6 1 5 3 4

Output 1

13

Note

First, JYY shoots at plot 1, and the number of rabbits in the plots becomes: 0 0 6 7 0 Then, JYY shoots at plot 4, and a total of 13 rabbits are eliminated.