АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1843. Автогонки

Ограничение времени: 1 сек.
Ограничение памяти:4096 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую. На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги A на дорогу B. Гонщик стартует в точке A0 и должен финишировать в точке BN. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A0A1, A1A2, ..., AN - 1AN, B0B1, B1B2, ..., BN - 1BN. Время прохождения всех переездов A0B0, A1B1, ..., ANBN одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу. Решения, верно работающие при количестве участков не более 10, будут оцениваться из 20 баллов.

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

В первой строке задаётся количество участков трассы 1 ≤ N ≤ 106. Во второй строке задаётся целое число 1 ≤ t ≤ 10000 – время (в секундах) прохождения каждого из переездов A0B0, A1B1, …, ANBN. В каждой из последующих N строк записано два целых числа 1 ≤ ai, bi ≤ 10000, задающих время (в секундах) прохождения очередного участка на каждой из дорог. В первой из этих строк указывается время прохождения участков A0A1 и B0B1, во второй – A1A2 и B1B2 и т. д.

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

Программа должна напечатать одно целое число: минимально возможное время прохождения трассы (в секундах).

Пример

Входные данные
3
20
320 150
200 440
300 210
Выходные данные
750

Все задачи турнира на одной странице


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Школьные олимпиады Вологодской области / Волбит-2018 /
1842. 09 - Треугольник наибольшей площади 1843.
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.