Опять Сайтама ненарочно уничтожил гостиницу. Чтобы расплатиться с гостиничной компанией, Генос вызвался управлять лифтом в одной из уцелевших гостиниц этой компании. Лифт обладает рядом особенностей: он всегда начинает движение с верхнего этажа, может двигаться только вниз и имеет бесконечную вместимость. Этажи пронумерованы от 0 до s, при этом лифт всегда находится на этаже номер s в момент времени 0.
Лифту требуется ровно 1 секунда, чтобы переместиться ровно на 1 этаж вниз. Временем, которое тратится на посадку и высадку пассажиров, можно пренебречь. У Геноса есть список, детально описывающий, когда и на какой этаж прибывает очередной пассажир. Пожалуйста, определите минимальное количество секунд, за которое можно доставить всех пассажиров на этаже номер 0.
Выходные данные
Выведите единственное целое число — минимальное количество времени в секундах, необходимое для того, чтобы высадить всех пассажиров на этаже с номером 0.
Примечание
В первом примере необходимо потратить не меньше 11 секунд, чтобы доставить всех пассажиров на этаж номер 0. Одним из способов это сделать является:
1. Доехать до этажа номер 5: занимает 2 секунды.
2. Взять пассажира номер 3.
3. Доехать до этажа номер 3: занимает 2 секунды.
4. Подождать, пока подойдет пассажир номер 2: занимает 4 секунды.
5. Взять пассажира номер 2.
6. Доехать до этажа номер 2: занимает 1 секунду.
7. Взять пассажира номер 1.
8. Доехать до этажа номер 0: занимает 2 секунды.
9. Высадить всех пассажиров.
Итого получается 2 + 2 + 4 + 1 + 2 = 11 секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 7
2 1
3 8
5 2
|
11
|
|
2
|
5 10
2 77
3 33
8 21
9 12
10 64
|
79
|