Фермер Джон получил груз из \(N\) больших стогов сена (\(1 \le N \le 4000\)) и разместил эти стога в различных точках дороги, ведущей к его амбару.
К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.
Каждый стог с номером \(j\) имеет размер \(S_j\) и уникальную позицию\(P_j\),
задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию.
В качестве исключения, если она движется в некотором направлении
\(D\) единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем \(D\). Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.
Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).
ФОРМАТ ВВОДА (файл trapped.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне \(1\ldots 10^9\).
ФОРМАТ ВЫВОДА (файл trapped.out):
Выведите целое число, определяющее длину части дороги из которой Беси не сможет сбежать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8 1
1 4
8 8
7 15
4 20
|
14
|