神孙权
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}帝者，国之权衡所归也！
\hspace{15pt}权衡利弊，制驭四方，保江东天下！
\hspace{15pt}审时度势，乃容万变。
\hspace{15pt}腹有锦绣千里，奈何偏居一隅。
\hspace{15pt}神孙权是三国杀OL的一个武将，他喜欢开启“东吴命运线”。

\hspace{15pt}神孙权有 k 张「手牌」。此外，还有 n 张牌排成一列，我们称它为「牌堆」，一端记为「牌堆顶」，另一端记为「牌堆底」。这些牌从「牌堆顶」到「牌堆底」依次编号为 1 到 n，第 i 张牌的价值记为 a_i。
\hspace{15pt}神孙权还有以下两个可以发动任意次的技能：
\hspace{23pt}\bullet\,「慎行」：你可以先弃置「手牌」中的 x 张牌，再从「牌堆」中摸 1 张牌加入「手牌」（x 为该技能此前发动次数）。弃置的牌会直接消失，不会再回到「牌堆」。如果「手牌」数量不足 x 或「牌堆」当中没有牌，则无法发动该技能。
\hspace{23pt}\bullet\,「帝力」：摸牌时，你可以选择从「牌堆顶」或「牌堆底」摸牌。请注意神孙权不可以从牌堆中间摸牌！
\hspace{15pt}神孙权希望通过合适的策略，使得从「牌堆」中摸出的牌的价值之和最大。这个价值之和最大可以到多少？

\hspace{15pt}只要神孙权摸到的牌就会被计入价值之和。即使这张牌后面被弃置了，也被会计入价值之和。

输入描述:

\hspace{15pt}第一行输入两个整数 n, k \left(1 \leq n \leq 10^5;\ 0 \leq k \leq 2\times 10^9\right) 代表「牌堆」中牌的数量、神孙权初始「手牌」的数量。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,a_3,\ldots,a_n \left(-10^9 \leq a_i \leq 10^9\right) 代表「牌堆」中从「牌堆顶」到「牌堆底」每张牌的价值。

输出描述:

\hspace{15pt}输出一个整数，代表神孙权从「牌堆」中摸出的牌的价值之和的最大值。
示例1

输入

复制 
5 2
10 -114514 3 4 5

输出

复制 
19

说明

\hspace{15pt}在样例中，神孙权的其中一种最佳策略是： 
\hspace{23pt}\bullet\,第一次行动，发动「慎行」，弃置 0 张牌，摸「牌堆顶」1 张牌后，剩余 3 张「手牌」； 
\hspace{23pt}\bullet\,第二次行动，发动「慎行」，弃置 1 张牌，摸「牌堆底」1 张牌后，剩余 3 张「手牌」； 
\hspace{23pt}\bullet\,第三次行动，发动「慎行」，弃置 2 张牌，摸「牌堆底」1 张牌后，剩余 2 张「手牌」。
\hspace{15pt}此时，因为手牌数不足 3 张，所以不能再发动技能。获得价值 10+5+4=19。
示例2

输入

复制 
4 773
0 -7 -2 -1

输出

复制 
0

说明

\hspace{15pt}神孙权可以选择不发动技能，获得最大价值 0。
示例3

输入

复制 
5 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

输出

复制 
5000000000

说明

\hspace{15pt}注意答案可能会超过 int 数据类型的数据范围。

备注: