Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов и собеседования. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов и собеседованию. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование. Если два кандидата с полупроходным баллом имеют одинаковый балл за собеседование, то проходит тот кандидат, значение ID которого выше.
Для данного множества кандидатов следует определить полупроходной балл, а также ID первого кандидата с набранным полупроходным баллом.
Входные данные
В первой строке входного файла находится два числа N – количество кандидатов (натуральное число, не превышающее 1000) и S – количество имеющихся мест.
Каждая из следующих N строк содержит пять чисел: ID кандидата (натуральное число, не превышающее 10 000 000), соответственно три оценки по экзаменам (все числа целые неотрицательные, не превышающие 100) и балл за собеседование (целое неотрицательное число, не превышающее 10).
Запишите в ответе два целых числа: сначала полупроходной балл, а затем ID первого кандидата с набранным полупроходным баллом.
Типовой пример организации данных во входном файле
7 3
1 90 90 90 10
3 60 70 80 8
5 63 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 7
2 79 65 72 6
При таких входных данных проходной балл равен 234, полупроходной 222, на оставшееся одно место будет назначен кандидат, набравший в сумме 215 баллов за экзамены и получивший по собеседованию 7 баллов.
Ответ для приведённого примера: 222; 11.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.