School Olympiad in Informatics was held for students of grades 7-11 participating in the general competition. Each participant of the Olympiad could score from 0 to 70 points. To determine the winners of the Olympiad, 25% of the participants who showed the best results are first selected. If the last participant in the 25% has the same number of points as those following him in the final table, they are all considered winners only when their points are more than half of the maximum possible. Otherwise, all of them are not considered winners.
Write a program that is efficient in terms of running time and memory used, which, based on the results of the Olympiad, will determine the minimum score of the winner of the Olympiad, and the number of winners in each parallel (among 7th, 8th, 9th, 10th and 11th grades separately). It is guaranteed that at least one winner can be determined according to the specified rules.
The number of participants in the Olympiad N is given as input to the program. Each of the following N lines contains the result of one of the participants in the Olympiad in the following format:
<Lastname> <Name> <class> <points>,
where <LastName> – a string of no more than 30 characters;
- <Name> – a string of no more than 15 characters;
- <class> – number from 7 to 11;
- <points> – an integer from 0 to 70 points scored by the participant.
<Surname> and <Name>, <Name> and <class> as well as <class> and <scores> separated by one space.
Input string example:
The program should display in the first line the minimum score of the winner, and in the next – the number of winners for all parallels separately.