UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3042. Acting Cute

统计 下载数据

Description

正在rainbow的城堡游玩的freda恰好看见了在地毯上跳舞卖萌的水叮当……于是……
freda:“呜咕>_< 我也要卖萌T_T!”
rainbow给了freda N秒的自由活动时间,不过由于刚刚游览城堡有些累了,freda只想花B秒的时间来卖萌,剩下的时间她要在rainbow的城堡里睡个好觉好好休息一下。
rainbow给这N秒每秒定义了一个值Ui,如果第i秒钟freda在卖萌,那么她可以获得Ui点卖萌指数lala~
freda开始卖萌后可以随时停止,休息一会儿之后再开始。不过每次freda开始卖萌时,都需要1秒来准备= =,这一秒是不能获得卖萌指数的。当然,freda卖萌和准备的总时间不能超过B。
更特殊的是,这N秒钟时间是环形的。也就是freda可以从任意时间开始她的自由活动并持续N秒。
为了使自己表现得比水叮当更萌,现在freda想知道,她最多能获得多少卖萌指数呢?

Input

第一行包含两个整数N和B。
第2~N+1行每行一个整数,其中第i+1行的整数表示Ui。

Output

输出一个整数,表示freda可以获得的最大卖萌指数。

Sample Input

5 3
2
0
3
1
4

Sample Output

6

对于100%的数据,0<=B<=N<=3600,0<=Ui<=200000。

样例解释:
freda选择从第2秒开始她的自由活动,持续N秒(2、3、4、5、1)。第4秒开始准备,第5、1秒卖萌(时间是环形的),获得2+4=6点卖萌指数。

Hint

Source

Poetize6