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

Условие

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

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

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

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

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

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

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

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

Ограничения

0 < t_max ≤ 10⁶, 0 < (t_i, m_i) ≤ t_max, t_i < t_i + 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

1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3

2 1210