Задача #2180

(PRO100 ЕГЭ) На олимпиаде по программированию задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение каждой задачи участник получает k баллов.

Вам, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение. Вы является талантливым школьником и поэтому сможете успешно решить за отведенное время и сдать на проверку любую задачу, которую выберете для решения на олимпиаде.

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

Входные данные
В первой строке входного файла находятся два числа: k – количество баллов за решение каждой задачи (натуральное число, не превышающее 100) и N – количество задач на олимпиаде (натуральное число, не превышающее 10 000). В следующих N строках находятся описания задач, по два числа на каждой строке: s_i – момент появления i-й задачи в минутах (натуральное число, не превышающее 10 000), t_i – время, отведенное на ее решение в минутах (натуральное число, не превышающее 10 000).

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

Пример входного файла:
6 5
1 2
2 3
1 2
3 1
3 2

При таких исходных данных можно решить максимум две задачи, следовательно получить за них 12 баллов. Минимальное время начала решения последней задачи, при условии решения двух задач 3.

Ответ для приведённого примера: 12 3.