Евгений занимается в Яндексе анализом больших данных. Недавно он решил немного отдохнуть, взял отпуск, и уехал в замечательный образовательный центр на берегу Чёрного моря преподавать школьникам машинное обучение и анализ данных.

По вечерам он идёт на набережную, где расположены n неплохих ресторанов, пронумерованных целыми числами 1, 2, ..., n, при этом ресторан с номером i находится на позиции i вдоль набережной. Евгений начинает в позиции 0 с запасом в e единиц энергии. Изначально желудок Евгения пуст и он тратит одну единицу энергии на перемещение в соседнюю позицию (например из позиции 0 в позицию 1, где расположен ресторан с номером 1). В течение вечера может происходить следующее.

1. Если в некоторый момент времени Евгений находится в позиции i и при этом он уже съел сегодня x единиц еды, то он может совершить операцию перемещения в позиции i - 1 или i + 1 потратив x + 1 единицу энергии.
2. Если Евгений находится в позиции i от 1 до n включительно и ещё не заходил этим вечером в ресторан с номеров i, то он может пойти туда. Евгений знает, что в результате посещения этого ресторана он съест ровно a_i единиц еды. На это действие Евгений не тратит энергии (жеванием можно пренебречь).
3. Если в некоторый момент времени Евгений снова оказывается в позиции 0, то он может принять решение остановится и пойти обратно в образовательный центр. Это действие так же не требует затрат энергии.

Поскольку Евгений занимается машинным обучением и смежными областями, он попросил вас посчитать максимальное количество еды, которое он может съесть и затем вернуться в образовательный центр в точке 0 если будет действовать оптимально.