Scholarship Selection for Maximum Median Score

You are given c students. The i-th student has a score \(a_i\) and requires a scholarship amount \(b_i\). You must select exactly n students to award scholarships. However, the total scholarship amount must not exceed \(f\). A mysterious benefactor wants the median score of the awarded students to be as high as possible. In this problem, the median is defined as the \(\lceil n/2 \rceil\)-th smallest score among the chosen students.

Determine the maximum achievable median score among the n selected students such that the sum of their scholarship amounts does not exceed \(f\). If no valid selection exists, output -1.

inputFormat

The first line contains three integers: c (number of students), n (number of students to select), and f (maximum total scholarship amount allowed).

Each of the next c lines contains two integers \(a_i\) and \(b_i\) representing the score and the required scholarship amount of the \(i\)-th student respectively.

It is guaranteed that \(n \le c\).

outputFormat

Output a single integer representing the maximum possible median score of the selected n students under the cost constraint. If no valid selection exists, output -1.

sample

5 3 10
5 3
1 1
4 2
3 2
2 3

4