Склад с двумя погрузчиками

На заводском складе к зоне погрузки подъезжают паллеты. Работают два одинаковых погрузчика.

Паллеты появляются в заданные моменты времени и становятся в одну общую очередь (в порядке появления). Если в момент появления паллеты есть свободный погрузчик и очередь пуста, погрузчик сразу берёт эту паллету. Если очередь не пуста, свободный погрузчик берёт первую паллету из очереди (правило FIFO).

Для каждой паллеты известна длительность погрузки. Пока погрузчик занят, он не может взять другую паллету.

Нужно узнать: 1) в какой момент времени будет загружена последняя паллета; 2) какой была максимальная длина очереди ожидания (паллеты, которые стоят и ждут, не считая двух паллет, которые могут одновременно грузиться).

Важно: времена могут быть большими (как на олимпиадах, могут не помещаться в 32-битный тип).

Формат ввода

В первой строке целое число n — количество паллет. Далее n строк: t_i d_i, где t_i — время появления i-й паллеты, d_i — длительность её погрузки. Паллеты даны в порядке неубывания t_i.

Формат вывода

Выведите два целых числа через пробел: T M, где T — время окончания погрузки последней паллеты, M — максимальная длина очереди ожидания.

Ограничения

• 1 ≤ n ≤ 100000
• 0 ≤ t_i ≤ 10^9, 1 ≤ d_i ≤ 10^9
• t_1 ≤ t_2 ≤ ... ≤ t_n

Пример

Ввод:

5
0 5
1 2
1 3
7 1
7 4

Вывод:

11 1

Ключевое наблюдение: важны не все моменты времени подряд, а только события — приход паллеты t_i и освобождение одного из двух погрузчиков. Между событиями ничего не меняется. Поэтому можно симулировать, храня всего два числа: когда освободятся погрузчики, и FIFO-очередь длительностей для тех, кто ждёт.

Почему работает: правило выбора всегда одно и то же — свободный погрузчик берёт первую паллету. Значит, если погрузчик освободился раньше следующего прихода и очередь не пуста, он обязан стартовать следующую паллету сразу в момент освобождения.

План:

• Заведи free1, free2 — моменты, когда погрузчики станут свободны (сначала 0).
• Заведи очередь q (например, deque) для длительностей ожидающих и max_q.
• Для каждой паллеты (t, d) по порядку:
• Пока q не пуста и какой-то freek <= t: освобождённый погрузчик берёт следующую паллету в момент freek и обновляет freek += dur.
• Добавь новую паллету в конец q.
• Если в момент t есть свободный погрузчик, он может взять из очереди (включая только что пришедшую), но старт не раньше t: ставь freek = t + dur.
• Обнови max_q = max(max_q, len(q)).
• После всех приходов «дослужи» оставшуюся очередь: каждый раз выбирай погрузчик с меньшим free и запускай следующую паллету в момент его освобождения.
• Ответ по времени: T = max(free1, free2).

Сложность: каждая паллета кладётся и снимается из очереди ровно один раз, значит O(n) по времени и O(n) по памяти.

Частая ошибка: считать длину очереди вместе с паллетами, которые уже грузятся. В len(q) должны быть только ожидающие, а две «в работе» учитываются через free1/free2.