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