Входной файл содержит информацию о времени прихода клиентов в банк, чтобы воспользоваться банкоматом, и длительность обслуживания клиента. С целью предотвращения возникновения большого скопления людей, каждый клиент подходит к свободному банкомату с максимальным номером. Банкоматы пронумерованы начиная с единицы. Клиент может воспользоваться только что освободившимся банкоматом в ту же минуту. Если в момент прихода клиента все банкоматы заняты, то клиент уходит. Определите максимальное общее время, которое один из банкоматов был занят за 24 ч, а также номер банкомата, которым воспользовалось наибольшее количество клиентов за сутки. Если таких банкоматов несколько, укажите минимальный номер из подходящих банкоматов.
Входные данные
В первой строке входного файла находится натуральное число K, не превышающее 1000, – количество банкоматов в банке. Во второй строке – натуральное число N (N ≤ 1000), обозначающее количество клиентов, желающих воспользоваться банкоматом. Каждая из следующих N строк содержит два натуральных числа: время прихода (в минутах от начала суток) и необходимое время (в минутах) для обслуживания клиента. Все числа натуральные, не превышают 10 000.
Запишите в ответе два числа: максимальное общее время обслуживания клиентов одним из банкоматов за 24 ч и наименьший номер банкомата, которым воспользовалось наибольшее количество клиентов за сутки.
Типовой пример организации данных во входном файле
2
5
675 90
716 90
723 72
818 62
1274 45
При таких исходных данных второй банкомат обслужил наибольшее количество клиентов. Максимальное время, когда один из банкоматов был занят, составляет 197.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.