Задача K. Очередь в поликлинике

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Очередь в поликлинике организована по талонам. Каждый пациент приходит строго к моменту, который указан в его талоне. При этом время приема врачом отдельно взятого пациента варьируется. Так, в некоторых случаях пришедшему вовремя пациенту придется ждать своей очереди, пока врач будет занят предыдущим посетителем.

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени ti, указанных в талоне каждого i-го пациента, и времени mi, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

При решении задачи следует полагать, что все ti и mi указывают время в минутах и могут принимать только целочисленные значения. Число минут в сутках полагается равным tmax.

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = tmax.

Формат входного файла

В начале входного файла "input.txt" содержится пара натуральных чисел tmax и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел ti и mi. При этом полагается, что все они упорядочены по возрастанию ti.

Формат выходного файла

Выходной файл "output.txt" должен содержать два значения: максимальную длину очереди и время завершения последнего приема.

Ограничения

0 < tmax ≤ 106, 0 < (ti, mi) ≤ tmax, ti < ti + 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3
0 1208
2
1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3
2 1210

0.076s 0.016s 13