На съезд прибыли коровы со всего мира.
На маленькой полянке есть очень редкая трава. Как результат, все 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 единиц времени.