В ловушке сена (бронза)
В ловушке сена (бронза)
Фермер Джон получил груз из n больших стогов сена и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.
Каждый стог с номером j имеет размер Sj
и уникальную позицию Pj
, задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении d единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем d. Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.
Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).
Входные данные
Первая строка ввода содержит n (1 ≤ n ≤ 4000). Каждая из последующих n строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне 1..109
.
Выходные данные
Выведите целое число, определяющее длину части дороги из которой Беси не сможет сбежать.
5 8 1 1 4 8 8 7 15 4 20
14