В университете имеется M бюджетных мест, на которые претендуют N абитуриентов. Абитуриентам предоставляются определённые критерии отбора для поступления – суммарное количество набранных баллов за все экзамены. Проходным баллом называется самый низкий балл абитуриента, которому предоставили бюджетное место. На бюджетные места зачисляются те абитуриенты, которые набрали как можно больше баллов за экзамены. Если несколько абитуриентов набрали одинаковое количество баллов, для них вводится следующий критерий – средний балл за аттестат. В таком случае, приоритет на поступление будет у того абитуриента, у которого средний балл аттестата будет выше.
Определите минимальный балл для зачисления в университет на бюджетное место, а также наибольший средний балл аттестата одного из абитуриентов, который не смогли набрать проходной балл.
Входные данные
В первой строке входного файла находятся два числа: M – количество бюджетных мест в университете и N – количество абитуриентов, претендующих на бюджетные места (N ≤ 10 000, N > M).
В каждой из следующих N строк находятся два числа: суммарное количество набранных баллов за экзамены и средний балл аттестата абитуриента.
Выходные данные
Запишите в ответе два числа: сначала проходной балл для зачисления на бюджетное место и наибольший возможный средний балл аттестата среди тех абитуриентов, что не набрали необходимый балл для поступления.
Пример входного файла:
3 5
300 5
289 5
260 3
280 4
248 4
При таких исходных данных первый, второй и четвёртый абитуриент займут бюджетные места. Минимальный балл для зачисления таким образом составит 280. Третий и пятый абитуриент не набрали необходимый балл для поступления, наибольший средний балл аттестата среди них равен 4.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.