Задача A. Безопасное пересечение дороги ≡

Автор:	И. Туфанов
Входной файл:	input.txt		Ограничение времени:	2 сек
Выходной файл:	output.txt		Ограничение памяти:	64 Мб

Условие

Пешеход переходит дорогу, состоящую из K полос автомобильного движения. Он заметил N автомобилей, каждый из которых движется по своей полосе движения w_i и пересечет место перехода дороги через b_i секунд. Пешеход может останавливаться между полосами дороги, а так же в начале и в конце пути. При этом, если он уже начал переходить полосу, то он не может остановиться и пересечение очередной полосы движения займет у него время t. В начальный момент времени пешеход находится на краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны. Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть он идет прямо и не поворачивает. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной i, если момент времени b_i он оказался на полосе w_i. Но если он в это время находился между полосами или в начале и в конце пути, то машина его не задевает.

Формат входного файла

Во входном файле содержатся числа K, N, t, за которыми следует N пар чисел w_i и b_i

Формат выходного файла

В выходной файл выведите единственное число - минимальное время, за которое переход может перейти дорогу. В приведенном ниже примере пешеход начинает переходить полосу 1 в начальный момент времени и заканчивает ее переходить через 10 секунд, как раз, когда по этой полосе проезжает машина 2. После этого он ждет 5 секунд и переходит вторую полосу.

Ограничения

0 ≤ N ≤ 2*10⁵, 1 ≤ K ≤ 2*10⁵, 1 ≤ t ≤ 10³, 0 ≤ b_i ≤ 10⁹

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	2 3 10 2 15 1 10 2 30	25

---

Задача B. КПК ≡

Автор:	И. Олейников, Т. Чистяков
Входной файл:	input.txt		Ограничение времени:	2 сек
Выходной файл:	output.txt		Ограничение памяти:	8 Мб

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

Вася собрал компьютер, но сомневается в правильности сборки. Напишите программу, которая по данному Васей описанию схемы определит, какие провода нужно удалить, какие оставить и какие придется добавить, чтобы компьютер был собран правильно. Так как Васе не хочется выполнять много работы, он просит вас удалять и добавлять провода таким образом, чтобы суммарное число добавленных и удаленных проводов было минимально.

Формат входного файла

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел a_i a_j, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

Формат выходного файла

Выходной файл содержит сначала число K₁ — количество проводов, которые нужно оставить в схеме, затем K₁ пар чисел a_i a_j — описание проводов. После этого следует число K₂ — число проводов, которые нужно добавить в схему, затем K₂ пар чисел a_i a_j — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 10⁶

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	3 1 2 3	1 2 3 1 1 2

---