[Jsoi2014]打兔子

内存限制：256 MiB 时间限制：20 Sec

勤劳的JYY在花园里面种了好多胡萝卜！可是，今天早上JYY发现一大群从JSOI王国里面跑来的兔子把他的花园全部

占满了！兔子们把胡萝卜吃光了，JYY靠什么过冬呢！忍无可忍的JYY决定取出他的强力猎枪来消灭这些兔子。JYY

的花园是一个由N个块小菜地顺次连接所形成的圆环。菜地由1到N编号。第i号菜地和第i+1号菜地是相邻的。由于

是环形的花园，所以1号菜地和N号菜地也是相邻的。现在，第i号菜地上有Ri只兔子。JYY的猎枪有K发子弹，每次J

YY可以选择一块菜地打一枪，然后这块菜地上的兔子就全部都被消灭了。但是由于JYY的猎枪威力太大，会吓到相

邻菜地上的兔子，所以，如果JYY朝i号菜地打了一枪，那么i+1号菜地上的兔子就会跑到i+2号菜地上去，同样的，

i-1号菜地上的兔子也会跑到i-2号菜地上去。JYY想知道，如何用这K发子弹，消灭尽量多的兔子呢？

输入文件的第一行包含两个整数N和K；

接下来一行N个整数，第i个整数为Ri。

3≤N≤4000，0≤K≤4000，0≤Ri≤10^5。

输出一行一个整数，表示JYY最多可以消灭的兔子个数。


			5 2

6 1 5 3 4


			13

【样例说明】

首先JYY朝1号菜地打一枪，然后菜地里面的兔子数量就变成了

0 0 6 7 0

接着JYY再朝4号菜地打一枪就可以一共消灭13只兔子了

#5038. [Jsoi2014]打兔子