F. Заказ футболок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это — очередной 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 не превосходит полного числа участников.

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

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

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

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