**Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Каждому файлу присвоен ранг важности -- целое число, которое показывает, насколько важную информацию содержит файл. По заданной информации об объёме файлов пользователей, их рангах важности и свободном объёме на архивном диске определите, какие файлы сохранить на диске, чтобы их суммарный ранг важности был максимальным. Если для приведённых данных есть несколько решений задачи, следует выбрать вариант, при котором остается меньше свободного места на архивном диске. Если и таких вариантов несколько, выбирается вариант, где самый большой файл имеет наибольший размер.
Входные данные. В первой строке входного файла 26-167.txt находятся два числа: S -- размер свободного места на диске (натуральное число, не превышающее 1 000 000) и N -- количество пользователей (натуральное число, не превышающее 10000). В каждой из следующих N строк находятся два числа: объём файла (натуральное число, не превышающее 5000) и его ранг важности (натуральное число, не превышающее 10). Запишите в ответе два числа: сначала максимальный суммарный ранг важности файлов, помещённых в архив, затем размер наибольшего файла, который был сохранён на диске.
Пример входного файла:
100 4
80 3
30 6
50 5
40 5
При таких исходных данных наибольший суммарный ранг важности (11) достигается при размещении на архивном диске пары файлов с объемами 30 и 50 или 30 и 40. Во втором случае на диске остается больше места, чем в первом, поэтому выбираем первый вариант. Ответ: 11 50.