Фермер Джон получили груз из n больших стогов сена, и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.
Каждый стог j имеет размер S[j]
и позицию P[j]
определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении d единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем d. Конечно после этого она может продолжить движение и таранить другие стога.
Беси может выйти на свободу если она в конце концов протаранит протаранит самый левый или самый правый стог. Вычислите общий размер участка дороги, состоящий из возможных точек старта Беси, из которых она не сможет выбраться.
Первая строка содержит n (1 ≤ n ≤ 10^5
). Каждая из последующих n строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1..10^9
. Все позиции различны.
Выведите одно целое число - размер области дороги, откуда Беси не сможет выбраться.