Конвенція II#10397

Конвенція II

1 секунда

128 мегабайтів

Середня

Незважаючи на тривалі затримки із зустріччю в аеропорту, конвенція Фермера Джона для корів, зацікавлених у поїданні трави, поки що проходить успішно. Вона привабила корів з усього світу.

Однак головна подія конвенції, схоже, може спричинити Фермеру Джону додаткові проблеми з розкладом. Дуже маленьке пасовище на його фермі має рідкісний сорт трави, яка, за словами вибагливих корів, є найсмачнішою у світі. Через це всі $n$ корів на конвенції хочуть скуштувати цю траву. Це, ймовірно, призведе до довгих черг, оскільки пасовище настільки маленьке, що може вмістити лише одну корову одночасно.

Фермер Джон знає час $a_{i}$ a_i, коли кожна корова $i$ планує прибути на особливе пасовище, а також кількість часу $t_{i}$ t_i, який вона планує провести, куштуючи траву, коли настане її черга. Щойно корова $i$ починає їсти, вона залишається протягом повних $t_{i}$ t_i одиниць часу, перш ніж піти, і протягом цього часу інші корови, що прибувають, мусять чекати. Якщо кілька корів чекають, коли пасовище знову звільняється, наступною куштувати траву дозволяється корові з найвищим старшинством. З цією метою корова, яка прибуває саме в той момент, коли інша корова закінчує їсти, вважається такою, що чекає. Аналогічно, якщо кілька корів прибувають точно в один і той самий час, коли жодна корова не їсть, наступною їсть та, що має найвище старшинство.

Допоможіть ФД обчислити максимальний час, який будь-якій корові доводиться чекати в черзі (між її часом прибуття $a_{i}$ a_i та моментом, коли вона починає їсти).

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Кожен з наступних $n$ рядків описує одну корову і містить два цілих числа $a_{i}$ a_i та $t_{i} (1 \leq a_{i} \leq 1 0^{9}, 1 \leq t_{i} \leq 1 0^{4})$ t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4). Корови перелічені в порядку старшинства, починаючи з найстаршої.

Вихідні дані

Виведіть одне ціле число — максимальний час очікування серед усіх корів.

Приклади

Приклад 1

Примітка

У цьому прикладі є $5$ корів, пронумерованих $1 \dots 5$ у порядку їх появи у вхідних даних. Корова $4$ прибуває першою (у момент часу $10$ ), і перш ніж вона закінчує їсти (у момент часу $27$ ), прибувають обидві корови $1$ і $3$ . Оскільки корова $1$ має вище старшинство, вона їсть наступною, прочекавши $2$ одиниці часу з моменту свого прибуття. Вона закінчує у момент часу $30$ , після чого корова $3$ починає їсти, прочекавши $10$ одиниць часу з моменту свого прибуття. Після періоду, коли жодна корова не їсть, прибуває корова $5$ , і поки вона їсть, прибуває корова $2$ ; корова $2$ починає їсти через $5$ одиниць часу після свого прибуття. Таким чином, корова, яка чекає найдовше, це корова $3$ .