Олимпиадный тренинг

Задача . F. Заказ футболок


Это — очередной Start[c]up, а значит, нужно опять заказывать футболки. Чтобы доставить футболки как можно быстрее, мы решили в этом году заказать все необходимые футболки до начала соревнования. Лучшие C участников будут награждены футболками, но мы не знаем, кто это будет. Наш план — узнать размер футболок для всех участников до соревнования, и затем заказать достаточно футболок, чтобы кто бы ни оказался среди C лучших участников, у нас было бы достаточно футболок для них.

Чтобы узнать размеры футболок, мы проведем опрос. Опрос позволит участникам либо выбрать один желаемый размер футболки, либо два соседних. Если участник выберет два соседних размера, это означает, что что ему подойдет любой из них.

Как вы можете догадаться, может понадобиться заказать много лишних футболок. Мы хотим попросить вас определить минимальное число футболок, которое нам нужно заказать, чтобы быть уверенным в том, что нам хватит футболок при любом результате соревнования.

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

В первой строке находятся два целых числа N и C (1 ≤ N ≤ 2·105, 1 ≤ C) — количество размеров футболок и количество участников, которые будут награждены.

Вторая строка содержит N - 1 целых чисел с s1 по sN - 1 (0 ≤ si ≤ 108). Для нечетных i, si равно количеству участников, которые выбрали размер футболки ((i + 1) / 2). Для четных i, si равно количеству участников, которые согласны получить размер (i / 2) или размер (i / 2 + 1). Гарантируется, что C не превосходит полного числа участников.

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

Выведите, какое минимальное число футболок мы должны купить.

Примечание

В первом примере мы можем купить 100 футболок каждого размера.


Примеры
Входные данныеВыходные данные
1 2 200
100 250 100
200
2 4 160
88 69 62 29 58 52 44
314

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя