Гьяччо хочет прогуляться по улицам Венеции. Однако он сегодня довольно раздражительный, что затрудняет прогулку.
Венеция является довольно популярным городом среди туристов, которые однако на иностранный манер называют город "Venice", вместо правильного "Venezia".
Это очень сильно злит Гьяччо, однако он не хочет остаться взбешенным после прогулки. Поэтому он решил, что иногда будет затыкать уши, проходя мимо туристов, чтобы не злиться лишний раз.
У Гьяччо есть внутренняя шкала спокойствия, которая пополняется на одну единицу в секунду (в момент выхода Гьяччо из дома значение этой шкалы равно нулю).
Однако если Гьяччо проходит мимо туристической группы, в которой d человек, то его спокойствие уменьшается на d, т.к. он злится из-за неправильного произношения названия города. Но если Гьяччо пройдет рядом, заткнув уши, то его спокойствие не уменьшиться.
Если в какой то момент времени шкала спокойствия станет отрицательной, то Гьяччо придет в бешенство, что является крайне недопустимым.
Гьяччо очень хорошо знает Венецию, поэтому он знает, что во время прогулки он пройдет около n туристических групп, для каждой из которых известно, что это будет в секунду с номером t
i и в этой группе будет d
i людей.
По данной информации посчитайте минимальное количество раз, когда Гьяччо придется затыкать уши, чтобы он не пришел в бешенство во время прогулки.
Входные данные:
В первой строке содержится единственное целое число n (1 ≤ n ≤ 200000) — количество туристических групп, около которых будет проходить Гьяччо.
Далее следуют n строк, каждая из которых содержит два целых числа через пробел: t
i и d
i (1 ≤ t
i, d
i ≤ 10
9) — номер секунды, в которую Гьяччо будет проходить мимо i-ой туристической группы, и количество человек в ней. Все t
i различны и упорядочены по возрастанию.
Выходные данные:
Выведите единственное целое число — минимальное количество раз, когда Гьяччо придется затыкать уши, чтобы не прийти в бешенство.
Примеры:
| Входные данные |
Выходные данные |
3
3 2
5 4
6 3 |
1 |
5
1 2
3 2
5 3
6 2
7 3 |
2 |
Пояснения:
В первом примере Гьяччо должен заткнуть уши, проходя около второй группы.
Тогда к концу третьей секунды его спокойствие будет равно 1 (3 он восполнил за каждую секунду прогулки, но уменьшил на 2 проходя мимо первой группы).
К концу пятой секунды спокойствие будет равно 3 (спокойствие не уменьшиться от второй группы, т.к. Гьяччо заткнул уши, проходя мимо).
И к концу шестой секунды спокойствие будет равно 3+1-3 = 1.
Далее его спокойствие никогда не уменьшается.