На съезд прибыли коровы со всего мира.
На маленькой полянке есть очень редкая трава. Как результат, все
\(N\) (\(1 \leq N \leq 10^5\)) коров, прибывших на конференцию, хотят
попробовать эту траву. Они выстраиваются в огромную очередь, поскольку
на полянке может быть в один момент времени только одна корова.
Фермер Джон знает время \(a_i\), в которое корова \(i\) планирует
прибыть на это пастбище, а также количество времени \(t_i\), которое
эта корова собирается провести на этом специальном пастбище.
После того, как корова \(i\) начинает есть траву, она делает это всё время
\(t_i\), в течение которого все вновь прибывшие коровы вынуждены ждать.
Если несколько коров ждут, когда пастбище освободится, корова с более
высоким старшинством будет следующей на поедание травы.
С этой целью корова, которая прибывает прямо, когда другая корова
завершает есть траву, называется "ожидающей". Аналогично, если
некоторое количество коров прибывает в один и тот же момент времени,
и никакая корова не ест, то корова с более высоким старшинством
принимается за еду.
Помогите ФД вычислить максимальное количество времени, которое придётся
ждать любой корове (между временем \(a_i\) и временем, когда она начнёт есть).
ФОРМАТ ВВОДА (файл convention2.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк указывает
детали \(N\) коров в порядке старшинства (более старшая корова - первая).
Каждая строка содержит \(a_i\) и \(t_i\) для одной коровы. \(t_i\) - положительные
целые числа, не превышающие \(10^4\), \(a_i\) - положительные целые числа,
не превышающие \(10^9\).
ФОРМАТ ВЫВОДА (файл convention2.out):
Выведите наибольшее потенциальное время ожидания среди всех коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
25 3
105 30
20 50
10 17
100 10
|
10
|