We all know that RI is the premier name in Singapore, JB (and some say Batam). As such, RI will only admit top students.
Students wishing to join the Raffles family need to go through multiple Convoluted Confusing Tests (CCT), and at the end they will be given a score between 1 and 2,000,000,000 (yes this CCT is -very- precise, much more precise than the Graded Poorly Always grade, better known as GPA).
RI also has high school fees, which not all students can afford. In fact, most students require some sort of financial support. The school however, only has a limited reserve fund 0 ≤ F ≤ 2,000,000,000.
Even worse, there are only enough classrooms for an odd number 1 ≤ N ≤ 1,000 of the 1 ≤ C ≤ 1,000 students who have applied to enter RI. The school admin wishes to admit exactly N students in order to maximise educational oppurtunity. The median of their CCT should be as high as possible.
Recall that the median of a set of integers whose size is odd is the middle value when they are sorted. For example, the median of the set {3, 8, 9, 7, 5} is 7, as there are exactly two values above 7 and exactly two values below it.
Give the score and financial aid for each student that applies, the total number of students to accept, and the total amount of money in the reserve, determine the maximum median score RI can obtain by admitting an optimal set of students.
Input
- Line 1: Three space-separated integers N, C, and F
- Lines 2..C+1: Two space-separated integers per line. The first is the student's CCT score; the second integer is the required amount of financial aid the student needs (≤ 2,000,000,000)
Output
- Line 1: A single integer, the maximum median score that the school admin can achieve. If there is insufficient money to admit N students, output -1.
Sample Input 1
3 5 70
30 25
50 21
20 20
5 18
35 30
Sample Output 1
35
Explanation for Sample Output 1
If the school admin accepts the students with CCT scores of 5, 35, and 50, the median is 35. The total financial aid required is 69, which is less than the max of 70.