Задача . A. SMS-центр

В некоторой большой организации, в которой работает Поликарп, находится собственный sms-центр. Задачей центра является рассылка сотрудникам различной важной информации. Поликарп решил проверить эффективность работы sms-центра.

Для этого он попросил предоставить ему данные о работе sms-центра за некоторый период времени. В ответ Поликарп получил список из n заданий, поступавших в sms-центр корпорации. Каждое задание описывалось временем поступления в sms-центр и количеством sms-сообщений, которое нужно было отослать. Более формально, i-ое задание описывалось двумя целыми числами t_i и c_i — моментом времени (секундой) поступления и количеством sms-сообщений соответственно.

Поликарп знает, что sms-центр может отсылать не более одного sms-сообщения в секунду. Для организации отправки сообщений sms-центр использует очередь. Рассмотрим некоторый момент времени x, sms-центр будет функционировать в момент времени x следующим образом:

1. Если в момент времени x очередь сообщений не пуста, тогда происходит отправка сообщения из очереди (сообщение берется из головы очереди). Иначе отправка сообщения в момент времени x не происходит.
2. Если в момент времени x поступило задание на отправку сообщений, то в очередь добавляются все сообщения из этого задания (сообщения добавляются в хвост очереди). Обратите внимание, ни одно из этих сообщений не может быть отправлено в момент времени x, так как решение об отправке или не отправке сообщения в момент времени x принимается в пункте 1 до добавления этих сообщений.

По результатам анализа выполнения всех n заданий Поликарп хочет посчитать две величины: момент времени, когда было отправлено последнее sms-сообщение, а также максимальный размер очереди в некоторый момент времени. Помогите ему посчитать эти две характеристики, по которым он оценит эффективность работы sms-центра.