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