D. Лучший отпуск
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы давно влюблены в Коронавирус-тян, но до сих пор не знали, где она живёт. И буквально сейчас выяснили, что она живёт в далёком местечке под названием Ньаху.

Вы немедленно решили взять отпуск на своей скучной работы и навестить Коронавирус-тян. Ваш отпуск длится ровно $$$x$$$ дней, и ровно столько дней вы проведёте в гостях у подруги. В гостях вы проведёте ровно $$$x$$$ подряд идущих дней.

В Ньаху используется очень необычный календарь: всего в году $$$n$$$ месяцев, $$$i$$$-й месяц длится ровно $$$d_i$$$ дней. Дни в $$$i$$$-м месяце пронумерованы от $$$1$$$ до $$$d_i$$$. В Ньаху нет високосных годов.

Настроение Коронавирус-тян (и, соответственно, её желание вас обнять) зависит от номера дня в месяце. А именно, в $$$j$$$-й день месяца вы получаете $$$j$$$ объятий, если вы находитесь в гостях у Коронавирус-тян.

Вы знаете об этой особенности своей подруги и хотите спланировать свою поездку так, чтобы суммарно получить наибольшее возможное количество объятий (и тогда, быть может, вы сможете завоевать сердечко Коронавирус-тян).

Обратите внимание, ваша поездка не обязательно должна начаться и закончиться в одном и том же году.

Входные данные

В первой строке входных данных даны два натуральных числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество месяцев в году и количество дней, которые вы можете провести в гостях у подруги.

Во второй строке даны $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$, где $$$d_i$$$ — количество дней в $$$i$$$-м месяце ($$$1 \le d_i \le 10^6$$$).

Гарантируется, что $$$1 \le x \le d_1 + d_2 + \ldots + d_n$$$.

Выходные данные

Выведите единственное число — максимальное число объятий, которое вы можете получить от Коронавирус-тян за время лучшего отпуска в своей жизни.

Примеры
Входные данные
3 2
1 3 1
Выходные данные
5
Входные данные
3 6
3 3 3
Выходные данные
12
Входные данные
5 6
4 2 3 1 3
Выходные данные
15
Примечание

В первом примере номера дней года (номера в соответствующих месяцах) имеет вид: $$$\{1,1,2,3,1\}$$$. Коронавирус-тян обнимет вас больше всего раз, если вы приедете в третий день года: $$$2+3=5$$$ объятий.

Во втором примере номера дней года (номера в соответствующих месяцах) имеет вид: $$$\{1,2,3,1,2,3,1,2,3\}$$$. Больше всего объятий вы получите если приедете в третий день года: $$$3+1+2+3+1+2=12$$$ объятий.

В третьем примере номера дней имеют вид: $$$\{1,2,3,4,1,2, 1,2,3, 1, 1,2,3\}$$$. Больше всего объятий вы получите если приедете в двенадцатый день года: подруга обнимет вас $$$2+3+1+2+3+4=15$$$ раз.