题目描述

勤劳的 JYY 在花园里面种了好多胡萝卜！可是，今天早上 JYY 发现一大群从 JSOI 王国里面跑来的兔子把他的花园全部占满了！兔子们把胡萝卜吃光了，JYY 靠什么过冬呢！忍无可忍的 JYY 决定取出他的强力猎枪来消灭这些兔子。

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

现在，第 $i$ 号菜地上有 $r_i$ 只兔子。JYY 的猎枪有 $k$ 发子弹，每次 JYY 可以选择一块菜地打一枪，然后这块菜地上的兔子就全部都被消灭了。但是由于 JYY 的猎枪威力太大，会吓到相邻菜地上的兔子，所以，如果 JYY 朝 $i$ 号菜地打了一枪，那么 $i+1$ 号菜地上的兔子就会跑到 $i+2$ 号菜地上去，同样的，$i-1$ 号菜地上的兔子也会跑到 $i-2$ 号菜地上去。JYY 想知道，如何用这 $k$ 发子弹，消灭尽量多的兔子呢？

输入格式

第一行两个整数 $n$ 和 $k$。

第二行 $n$ 个整数，第 $i$ 个为 $r_i$。

输出格式

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

5 2
6 1 5 3 4

13

提示

样例解释

先朝 $1$ 号菜地打一枪，变成 $0\ 0\ 6\ 7\ 0$，再朝 $4$ 号菜地打一枪。可以证明没有比 $13$ 大的答案。

数据范围

对于 $100\%$ 的数据，$3\leq n\leq 4000,0\leq k\leq 4000,r_i\leq 10^5$