MemSQL Start[c]UP 3.0 - Round 1 |
---|
Закончено |
Это — очередной Start[c]up, а значит, нужно опять заказывать футболки. Чтобы доставить футболки как можно быстрее, мы решили в этом году заказать все необходимые футболки до начала соревнования. Лучшие C участников будут награждены футболками, но мы не знаем, кто это будет. Наш план — узнать размер футболок для всех участников до соревнования, и затем заказать достаточно футболок, чтобы кто бы ни оказался среди C лучших участников, у нас было бы достаточно футболок для них.
Чтобы узнать размеры футболок, мы проведем опрос. Опрос позволит участникам либо выбрать один желаемый размер футболки, либо два соседних. Если участник выберет два соседних размера, это означает, что что ему подойдет любой из них.
Как вы можете догадаться, может понадобиться заказать много лишних футболок. Мы хотим попросить вас определить минимальное число футболок, которое нам нужно заказать, чтобы быть уверенным в том, что нам хватит футболок при любом результате соревнования.
В первой строке находятся два целых числа N и C (1 ≤ N ≤ 2·105, 1 ≤ C) — количество размеров футболок и количество участников, которые будут награждены.
Вторая строка содержит 2·N - 1 целых чисел с s1 по s2·N - 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 футболок каждого размера.
Название |
---|