У пастці сіна (бронза)#11168
Фермер Джон отримав партію з великих тюків сіна і розмістив їх у різних місцях уздовж дороги, що веде до його амбару. На жаль, він зовсім забув, що корова Бессі пасеться вздовж цієї дороги, і тепер вона може опинитися замкненою між тюками сіна!
Кожен тюк має розмір S_j та унікальну позицію P_j на цій одновимірній дорозі. Бессі починає рух з деякої точки, в якій немає тюка сіна. Вона може вільно переміщатися вздовж дороги, зокрема дійти до позиції, де знаходиться тюк, але не може пройти крізь нього. Однак є виняток: якщо вона біжить в одному й тому ж напрямку на відстань , вона набирає достатньої швидкості, щоб пробити і назавжди знищити будь-який тюк сіна, розмір якого строго менший за . Звісно, після знищення одного тюка у неї може з'явитися достатньо вільного простору, щоб знову розігнатися в напрямку іншого тюка і також знищити його.
Бессі може вибратися на волю, якщо їй зрештою вдасться пробити або найлівіший, або найправіший тюк сіна. Ваше завдання — обчислити загальну довжину дороги, що складається з усіх дійсних початкових позицій, з яких Бессі не може вибратися. Наприклад, якщо Бессі не може вибратися, починаючи з будь-якої точки між тюками сіна, розташованими в позиціях та , то цей інтервал додає до відповіді довжину .
У першому рядку міститься ціле число n~(1 \le n \le 4000).
У кожному з наступних рядків містяться два цілих числа, що описують один тюк сіна: його розмір S_j та позицію P_j. Усі розміри та позиції знаходяться в діапазоні від до 10^9.
Виведіть одне ціле число: загальну довжину дороги, з якої Бессі не може вибратися.
Приклад 1