P3963 [TJOI2013] Scholarship

Xiao Zhang recently published a paper, and a mysterious person wants to award scholarships to Xiao Zhang's college.

There are $c$ students in Xiao Zhang's college. The $i$-th student's score is $a_i$, and the scholarship amount they would receive is $b_i$. You need to select $n$ students from these $c$ students to award scholarships. This mysterious person has a peculiar preference: he wants the median of the scores of the students who receive scholarships to be as large as possible, while their total scholarship amount must not exceed $f$.

The first line contains three integers, representing the number of students to select $n$, the total number of students $c$, and the maximum total scholarship amount $f$, **guaranteeing that $n$ is odd**. Lines $2$ through $(c + 1)$: each line contains two integers. The $(i + 1)$-th line contains the $i$-th student's score $a_i$ and, if they are awarded a scholarship, the amount $b_i$ that needs to be given.

Output one integer on a single line representing the answer. If the mysterious person's conditions cannot be met, output $-1$.

### Sample 1 Explanation Select three students with scores $5$, $35$, and $50$, with a total scholarship amount of $18 + 30 + 21 = 69$. ### Constraints - For $30\%$ of the testdata, it is guaranteed that $n \leq 10^3$, $c \leq 2 \times 10^3$. - For $100\%$ of the testdata, it is guaranteed that $3 \leq n \leq 10^5$, $n \leq c \leq 2 \times 10^5$, $0 \leq f \leq 2 \times 10^9$, $0 \leq a_i \leq 2 \times 10^9$, $0 \leq b_i \leq 10^5$. Translated by ChatGPT 5