Пешеход
переходит дорогу, состоящую из 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
Примеры тестов
|
№
|
Входной файл
|
Выходной файл
|
|
1
|
2 3 10
2 15
1 10
2 30
|
25
|
