Вася сидит за компьютером. Иногда ему приходят уведомления о том, что на его любимом 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.
Название |
---|