Сдать задачи.

1. Гоночная трасса 1.

   
   Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую.
   На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги A на дорогу B. Гонщик стартует в точке A0 и должен финишировать в точке BN. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A0-A1, A1-A2, ..., A(N-1)-AN, B0-B1, B1-B2, ..., B(N-1)-BN. Время прохождения всех переездов A0-B0, A1-B1, ..., AN-BN одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу.
   Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
   
   Входные данные
   В первой строке задаётся количество участков трассы N. Во второй строке задаётся целое число t – время (в секундах) прохождения каждого из переездов A0-B0, A1-B1, …, AN-BN. В каждой из последующих N строк записано два целых числа ai и bi, задающих время (в секундах) прохождения очередного участка на каждой из дорог. В первой из этих строк указывается время прохождения участков A0-A1 и B0-B1, во второй – A1-A2 и B1-B2 и т. д.
   
   Пример входных данных
   3
   20
   320 150
   200 440
   300 210
   
   Выходные данные
   Программа должна напечатать одно целое число: минимально возможное
   время прохождения трассы (в секундах).
   
   Пример выходных данных для приведённого выше примера входных данных
   750




2. Гоночная трасса 2.

   
   Автомобиль, участ­ву­ю­щий в гонке, может быть осна­щен двумя раз­ны­ми типами колес (A и B). Вдоль трас­сы расположены станции, на ко­то­рых можно вы­пол­нить замену колес A на B, эта опе­ра­ция занимает t секунд. За­ме­на колес B на A в ходе гонки тех­ни­че­ски невозможна. На старт можно выйти с любым комплектом. Для каж­до­го участка между стан­ци­я­ми известно, за какое время можно прой­ти этот уча­сток с каж­дым из ком­плек­тов колес. Не­об­хо­ди­мо определить, за какое ми­ни­маль­ное время можно прой­ти всю трассу.
   Напишите про­грам­му для ре­ше­ния этой задачи.
   Перед тек­стом программы крат­ко опишите ал­го­ритм решения и ука­жи­те язык про­грам­ми­ро­ва­ния и его версию.
   Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
   Задание А. Имеются данные о времени прохождения участков трассы с различными типами колёс. Всего пунктов 10 штук. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
   Максимальная оценка за правильную программу – 2 балла.
   Задание Б. Имеются данные о времени прохождения участков трассы с различными типами колёс. Пунктов может быть очень много. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
   Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
   Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
   Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
   Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
   
   Входные данные
   В пер­вой строке за­да­ет­ся количество участ­ков трассы N. Во вто­рой строке за­да­ет­ся целое число t — время (в секундах) на за­ме­ну колес A на B. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но два целых числа ai и bi, за­да­ю­щих время (в секундах) про­хож­де­ния очередного участ­ка с каж­дым из комплектов. В пер­вой из этих строк ука­зы­ва­ет­ся время про­хож­де­ния участка от стар­та до пер­вой станции, во вто­рой – от пер­вой станции до вто­рой и т. д.
   
   Пример вход­ных данных
   3
   10
   130 210
   320 140
   100 120
   
   Выходные данные
   Программа долж­на напечатать одно целое число: ми­ни­маль­но возможное время про­хож­де­ния трассы (в секундах).
   
   Пример вы­ход­ных дан­ных для приведённого выше при­ме­ра вход­ных данных
   400