Byteasar 决定在他的花园里种植生菜。正如你所料，Bytean 兔子非常喜欢生菜，所以不出所料，它们立刻就来到了 Byteasar 的花园里。

花园里有 $n$ 个生菜苗圃，编号为 $1$ 到 $n$。每两个相邻的苗圃都是相邻的，也就是说，对于每个 $i = 1, 2, \dots, n-1$，编号为 $i$ 和 $i+1$ 的苗圃相邻；此外，编号为 $n$ 的苗圃与编号为 $1$ 的苗圃也相邻。目前，编号为 $i$ 的苗圃中有 $a_i$ 只兔子正在吃 Byteasar 的生菜。

Byteasar 想要尽可能多地将兔子赶出花园。为此，他打算使用他的老式猎枪。这把枪里有 $k$ 发子弹。兔子非常胆小，所以每当 Byteasar 向编号为 $i$ 的苗圃射击时，该苗圃中的所有兔子都会永远离开 Byteasar 的花园。不仅如此，两个相邻苗圃中的兔子也会因为受到惊吓而移动到另一个相邻的苗圃中（显然，是指除了被射击的那个苗圃之外的另一个相邻苗圃）。

请帮助 Byteasar 计算出他最多使用 $k$ 发子弹能赶出花园的兔子总数的最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($5 \le n \le 2000, 1 \le k \le n$)：花园中苗圃的数量和 Byteasar 枪中的子弹数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$)：各个苗圃中兔子的数量。

输出格式

输出一个整数：使用最多 $k$ 发子弹能从 Byteasar 的花园中赶出的兔子的最大数量。

样例

输入 1

5 2
6 1 5 3 4

输出 1

13

说明

样例解释：首先，Byteasar 赶走了 1 号苗圃中的 6 只兔子（结果是，5 号苗圃的兔子移动到了 4 号苗圃，而 2 号苗圃的兔子移动到了 3 号苗圃）。接下来，Byteasar 赶走了 4 号苗圃中的 7 只兔子。