2957. Naptime

【题目描述】

正在rainbow的城堡游玩的freda恰好看见了在地毯上跳舞卖萌的水叮当……于是……

freda：“呜咕>_< 我也要卖萌T_T！”

rainbow给了freda $N$秒的自由活动时间，不过由于刚刚游览城堡有些累了，freda只想花$B$秒的时间来卖萌，剩下的时间她要在rainbow的城堡里睡个好觉好好休息一下。

rainbow给这$N$秒每秒定义了一个值$U_i$，如果第$i$秒钟freda在卖萌，那么她可以获得$U_i$点卖萌指数lala~

freda开始卖萌后可以随时停止，休息一会儿之后再开始。不过每次freda开始卖萌时，都需要1秒来准备= =，这一秒是不能获得卖萌指数的。当然，freda卖萌和准备的总时间不能超过B。

更特殊的是，这$N$秒钟时间是环形的。也就是freda可以从任意时间开始她的自由活动并持续N秒。

为了使自己表现得比水叮当更萌，现在freda想知道，她最多能获得多少卖萌指数呢？

【输入格式】

第一行包含两个整数$N$和$B$。

第$2~N+1$行每行一个整数，其中第$i+1$行的整数表示$U_i$。

【输出格式】

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

【样例输入】

5 3
2
0
3
1
4

【样例输出】

6

【提示】

对于60%的数据，$N<=100$

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

样例解释：

freda选择从第2秒开始她的自由活动，持续N秒（2、3、4、5、1）。第4秒开始准备，第5、1秒卖萌（时间是环形的），获得2+4=6点卖萌指数。

【来源】

《算法竞赛进阶指南》  POJ 2228  USACO 2005 January Gold