Problem B
Grading on a Curve
![/problems/gradingonacurve/file/statement/en/img-0001.jpg](/problems/gradingonacurve/file/statement/en/img-0001.jpg)
Professor Peggert is famous for his exams with low average / median scores and no extra credit. Despite this, his students’ final grades (usually) turn out okay, as he boosts everyone’s score by grading on a curve. Professor Peggert determines final grades by choosing a positive integer $K$ and dividing each student’s score by $K$ to get a percentage representing that student’s grade. For example, if a student scored $5$ on a $12$ point exam, and $K$ is chosen to be $10$, the student would have received a $5/K=50\% $. He wants to choose a number $K$ that satisfies the following conditions:
-
At least a quarter of the class should receive a final grade of $90\% $ (A-) or better;
-
At least half of the class should receive a final grade of $80\% $ (B-) or better;
-
At least three quarters of the class should receive a final grade of $70\% $ (C-) or better.
Professor Peggert doesn’t want to curve the grades too generously though, so he wants $K$ to be as high as possible while satisfying the previous conditions. Note that the $K$ chosen may be any positive integer, even if the chosen $K$ results in some final grades being more than $100\% $.
Input
The first line contains two space-separated integers $1 \leq N,T \leq 100\, 000$, where $N$ is the number of students and $T$ is the maximum possible score that a student can score on the test. Each of the following $N$ lines contains an individual student’s test score $0 \leq T_ i \leq T$ where $T_ i$ is an integer.
Output
Output one line containing the highest number $K$ that satisfies the conditions. Output $-1$ if no such number exists.
Sample Input 1 | Sample Output 1 |
---|---|
4 10 5 6 7 8 |
8 |
Sample Input 2 | Sample Output 2 |
---|---|
4 100 76 53 83 67 |
92 |
Sample Input 3 | Sample Output 3 |
---|---|
4 10 10 0 10 0 |
-1 |