M. Уведомления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася сидит за компьютером. Иногда ему приходят уведомления о том, что на его любимом Youtube-канале вышло новое видео. Тогда,

  • если в данный момент он не смотрит видео, он кликает на уведомление и начинает смотреть это видео до конца,
  • если в данный момент он смотрит видео, он сначала посмотрит все непросмотренные видео, о которых уже пришли уведомления до этого, а потом кликнет на новое уведомление и посмотрит новое видео до конца.

Вам дано $$$n$$$ параметров уведомлений: $$$i$$$-е уведомление пришло в момент времени $$$t_i$$$ и содержит видео длины $$$d_i$$$. Выведите, когда Вася закончит смотреть последнее видео.

Входные данные

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 200000$$$) — количество уведомлений.

В каждой из следующих $$$n$$$ строк даны два числа $$$t_i$$$ и $$$d_i$$$ ($$$1 \le t_i, d_i \le 10^9$$$) — время, когда Васе пришло $$$i$$$-е уведомление и длина видео, которое содержится в этом уведомлении.

Все $$$t_i$$$ образуют неубывающую последовательность, т. е. $$$t_i \le t_{i+1}$$$ для всех $$$i$$$ от 1 до $$$(n-1)$$$.

Выходные данные

Выведите единственное целое число — момент времени, когда Вася закончит смотреть последнее видео.

Пример
Входные данные
5
1 4
3 3
6 1
10 2
10 3
Выходные данные
15
Примечание

В приведенном примере последовательность просмотров Васи будет следующей:

1) В момент времени 1 Вася получит уведомление о видео длительностью 4. Так как на тот момент он не смотрит видео, то Вася начнет смотреть данное видео до момента времени 5.

2) В момент времени 3 Вася получит уведомление о видео длительностью 3, но в этот момент он будет занят просмотром первого видео, поэтому данное видео он начнет смотреть в момент времени 5 (после первого) до момента времени 8.

3) В момент времени 6 Вася получит уведомление о видео длительностью 1 и посмотрит его с момента времени 8 до момента времени 9.

4) С момента времени 9 до момента времени 10 Вася не делает ничего.

5) В момент времени 10 Вася получает сразу два уведомления — о видео длительностью 2 и 3. Вася будет их смотреть в порядке поступления, поэтому сначала посмотрит видео с 10 до 12, а затем — с 12 до 15.