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

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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 2 * 105, 1 ≤ K ≤ 2 * 105, 1 ≤ t ≤ 103, 0 ≤ bi ≤ 109

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

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

0.075s 0.012s 13