Поликарп разрабатывает уровень для игры. Уровень состоит из \(n\) отрезков на числовой прямой, \(i\)-й отрезок начинается в точке с координатой \(l_i\) и заканчивается в точке с координатой \(r_i\).
Игрок начинает уровень в точке с координатой \(0\). За один ход он может переместиться на любую точку, расстояние до которой не больше \(k\). После своего \(i\)-го хода игрок должен оказаться в \(i\)-м отрезке, то есть в такой координате \(x\), что \(l_i \le x \le r_i\). То есть:
- После первого хода он должен оказаться внутри первого отрезка (от \(l_1\) до \(r_1\));
- После второго хода он должен оказаться внутри второго отрезка (от \(l_2\) до \(r_2\));
- ...
- После \(n\)-го хода он должен оказаться внутри \(n\)-го отрезка (от \(l_n\) до \(r_n\)).
Уровень считается пройденным, если игрок добрался до \(n\)-го отрезка, следуя правилам, описанным выше. Немного подумав, Поликарп понял, что при некоторых \(k\) пройти уровень невозможно.
Поликарп не хочет, чтобы уровень был слишком простым, поэтому просит вас определить минимальное целое число \(k\), при котором его возможно пройти.
Примечание
В третьем примере игрок может сделать следующие ходы:
- Переместиться из точки \(0\) в точку \(5\) (\(3 \le 5 \le 8\));
- Переместиться из точки \(5\) в точку \(10\) (\(10 \le 10 \le 18\));
- Переместиться из точки \(10\) в точку \(7\) (\(6 \le 7 \le 11\)).
Обратите внимание, что последним ходом игрок мог не перемещаться и всё равно пройти уровень.