Remote Training on Programming

Пешеход переходит дорогу, состоящую из 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⁹

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

2 3 10

2 15

1 10

2 30

25