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