406848: GYM102569 M Notifications

Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then,

• if he isn't watching any video at the moment, he clicks the notification and starts to watch this video till the end,
• if he is already watching a video at the moment, he will firstly watch all unfinished videos (about which he received notification earlier), and then click the new notification and watch the new video till the end.

You are given $$$n$$$ parameters of the notifications: the $$$i$$$-th notification is received at the moment of time $$$t_i$$$ and contains the video of length $$$d_i$$$. Find when Vasya will stop watching the last video.

The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of notifications.

Each of the next $$$n$$$ lines contains two integers $$$t_i$$$ and $$$d_i$$$ ($$$1 \le t_i, d_i \le 10^9$$$) — the moment of time when Vasya receives the $$$i$$$-th notification, and the length of the video in this notification.

All $$$t_i$$$ form non-decreasing sequence, i. e. $$$t_i \le t_{i+1}$$$ for all $$$i$$$ from 1 to $$$(n-1)$$$.

Output one integer — the moment of time when Vasya will stop watching the last video.

5
1 4
3 3
6 1
10 2
10 3

15

In the given example the sequence of Vasya's actions is the following:

1) At the moment 1 he receives a notification about the video of length 4. As he isn't watching any video at the moment, he starts to watch it till the moment of time 5.

2) At the moment 3 he receives a notification about the video of length 3, but he is watching the first video at the moment, so he will start watching this video at the moment 5 (just after the first one) and finish at the moment 8.

3) At the moment 6 he receives a notification about the video of length 1. He will watch it from the moment 8 to the moment 9.

4) From the moment 9 to the moment 10, Vasya is not doing anything.

5) At the moment 10 he receives two notification — about the videos of lengths 2 and 3. He will watch them in the order he receives them, so he will watch the first of them from 10 to 12, and the other one — from 12 to 15.