Угода II
На з'їзд прибули корови з усього світу.
На маленькій галявині росте дуже рідкісна трава. Усі n корів, що прибули на конференцію, хочуть скуштувати цю траву. Вони шикуються в довгу чергу, оскільки на галявині може бути лише одна корова одночасно.
Фермер Джон знає час a[i], коли корова i планує прибути на пасовище, а також час t[i], який вона збирається провести на ньому. Як тільки корова i починає їсти траву, вона робить це протягом t[i] одиниць часу, і всі новоприбулі корови змушені чекати. Якщо кілька корів чекають, коли пасовище звільниться, корова з вищим старшинством буде наступною. Корова, яка прибуває в момент, коли інша корова завершує їсти траву, вважається "очікуючою". Якщо кілька корів прибувають одночасно, і жодна не їсть, то корова з вищим старшинством починає їсти першою.
Допоможіть фермеру Джону обчислити максимальний час очікування, який може знадобитися будь-якій корові (між часом a[i] і моментом, коли вона почне їсти).
Вхідні дані
Перший рядок вводу містить n (1 ≤ n ≤ 10^5). Кожен з наступних n рядків описує деталі n корів у порядку старшинства (більш старша корова - перша). Кожен рядок містить a[i] і t[i] для однієї корови. t[i] - позитивні цілі числа, що не перевищують 10^4, a[i] - позитивні цілі числа, що не перевищують 10^9.
Вихідні дані
Виведіть найбільший можливий час очікування серед усіх корів.
Приклад
У цьому прикладі є 5 корів (пронумерованих від 1 до 5 в порядку вводу). Корова 4 прибуде першою (в момент часу 10), і перш ніж вона закінчить їсти, прибудуть корови 1 і 3. Оскільки корова 1 має вище старшинство, вона буде їсти наступною, почекавши 2 одиниці часу. Вона закінчить в момент часу 30, і тоді почне їсти корова 3, почекавши 10 одиниць часу до початку їжі. Потім буде перерва, коли ніхто не їсть. Потім прибуває корова 5, і поки вона їсть, прибуває корова 2 і починає їсти через 5 одиниць часу. Корова, яка чекала найдовше, має номер 3 і вона чекала 10 одиниць часу.