Problem 3: Airplane Boarding [Travis Hance]
Коровы прибыли в в аэропорт и столкнулись с интересной проблемой.
В самолёте имеется N мест, которые мы моделируем как точки от x=1 до x=N на числовой прямой. Все N коров (1 <= N <= 200,000) стоят в ряд, ожидая занятия своего места. Корова N стоит на позиции x=0, корова N-1 на позиции x=-1 и т.д. Корове I назначено место Si, где S1, S2, … - это перестановка чисел от 1 до N.
Каждую секунду каждая корова делает шаг вправо, если она может. Когда корова I достигает своего места Si, она останавливается, чтобы положить багаж в верхний отсек салона, это занимает у неё Ti секунд, затем она садится. В течение этих Ti секунд, следующая за этой корова (если она есть) блокируется и не может двигаться вперёд. Если за ней вплотную стоят коровы, то они тоже все блокируются.
Сколько времени займёт посадка?
Сумма всех Ti будет меньше чем 1,000,000,000.
PROBLEM NAME: boarding
Формат входных данных
* Строка 1: Одно целое число, N.
* Lines 2..N+1: Два разделённых пробелом целых числа, Si и Ti.
Формат выходных данных
* Строка 1: Одно целое число, задающее количество времени, которое потребуется, чтобы все коровы заняли свои места.
Примечание
После первой секунды, все сдвинутся на 1 вправо и корова 3 достигнет своего места:
123 123
Корове 3 потребуется 5 секунд, чтобы сесть, после чего она «исчезает».
12 123
Потребуется еще 3 секунды коровам 1 и 2 чтобы добраться до своих мест:
12 123
Корове 1 потребуется 5 секунд, чтобы сесть, корове 2 – 10, поэтому ВСЕ усядутся через 10 секунд.
Общее время посадки: 1 + 5 + 3 + 10 = 19 секунд
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 5
3 10
1 5
|
19
|