Вы давно влюблены в Коронавирус-тян, но до сих пор не знали, где она живёт. И буквально сейчас выяснили, что она живёт в далёком местечке под названием Ньаху.
Вы немедленно решили взять отпуск на своей скучной работы и навестить Коронавирус-тян. Ваш отпуск длится ровно \(x\) дней, и ровно столько дней вы проведёте в гостях у подруги. В гостях вы проведёте ровно \(x\) подряд идущих дней.
В Ньаху используется очень необычный календарь: всего в году \(n\) месяцев, \(i\)-й месяц длится ровно \(d_i\) дней. Дни в \(i\)-м месяце пронумерованы от \(1\) до \(d_i\). В Ньаху нет високосных годов.
Настроение Коронавирус-тян (и, соответственно, её желание вас обнять) зависит от номера дня в месяце. А именно, в \(j\)-й день месяца вы получаете \(j\) объятий, если вы находитесь в гостях у Коронавирус-тян.
Вы знаете об этой особенности своей подруги и хотите спланировать свою поездку так, чтобы суммарно получить наибольшее возможное количество объятий (и тогда, быть может, вы сможете завоевать сердечко Коронавирус-тян).
Обратите внимание, ваша поездка не обязательно должна начаться и закончиться в одном и том же году.
Выходные данные
Выведите единственное число — максимальное число объятий, которое вы можете получить от Коронавирус-тян за время лучшего отпуска в своей жизни.
Примечание
В первом примере номера дней года (номера в соответствующих месяцах) имеет вид: \(\{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\) раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 1
|
5
|
|
2
|
3 6
3 3 3
|
12
|
|
3
|
5 6
4 2 3 1 3
|
15
|