АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
Forgot your password?
Authors ranklist
 
About project
Hello, Guest! Please login or register.

1843. Car racing

Time Limit: 1 seconds
Memory Limit:262144KB
Points:100
View Problem Statistics Submit Problem added 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

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

View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests and Camps / School olympiads and couses of Vologda region / VolBIT / VolBit-2018 /
1842. 09 - Triangle of maximal area 1843.
Problems from Contests and Camps / School olympiads and couses of Vologda region / Different Contests / Contest based on EGE /
1842. 03 - Triangle of maximal area 1843. 1867. 05 - Accelerator 1868. 06 - Photon 1869. 07 - Sequence
Problems from Contests and Camps / School olympiads and couses of Vologda region / Impulse, August-September 2022 / Impulse, August-September 2022, Opening Olympiad /
1839. 07 - Радиотелескоп 1843.
time generating 0.093 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.