Задача B. Небезопасное пересечение дороги

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

Условие

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

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

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

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

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

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

Ограничения

0 ≤ N ≤ 2*105, 1 ≤ K,t ≤ 100, 0 ≤ bi ≤ 104, 1 ≤ wi ≤ K

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

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

0.035s 0.007s 15