Exterminating Rabbits in the Circular Garden

Hardworking JYY planted many carrots in his garden. However, this morning he discovered that a horde of rabbits from the JSOI Kingdom have invaded and eaten all his carrots! Desperate for winter, JYY decided to take out his powerful shotgun to exterminate the rabbits.

The garden is arranged as a circular ring of n contiguous plots numbered from 1 to n. For every plot i, plot i is adjacent to plot i+1 (and because the garden is circular, plot n is adjacent to plot 1). Initially, plot i contains r_i rabbits.

JYY has k bullets. When he fires a bullet at a chosen plot, all the rabbits in that plot are exterminated. However, the blast scares the rabbits in the two adjacent plots. More precisely, if JYY shoots plot i:
- All rabbits in plot i are killed immediately.
- The rabbits in the next plot (i.e. plot i+1) run to plot i+2.
- Similarly, the rabbits in the previous plot (i.e. plot i-1) run to plot i-2.

Note that indices are computed modulo n (i.e. if an index is less than 1 or greater than n you should wrap around to the other end of the circle).

Your task is to determine the maximum number of rabbits JYY can exterminate using exactly k bullets by choosing an optimal shooting order.

Hint: The order in which plots are shot matters because the rabbit counts change due to the scared rabbits moving into other plots. Use an appropriate search (for example, DFS with memoization) to try all possibilities if n and k are small.

inputFormat

The input consists of two lines. The first line contains two integers n and k (the number of plots and the number of bullets). The second line contains n integers: r1, r2, ..., rn, representing the number of rabbits in each plot initially.

outputFormat

Output a single integer, the maximum number of rabbits that can be exterminated.

sample

4 1
10 20 30 40

40