Description

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$.

Input Format

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 Format

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

3 5 70
30 25
50 21
20 20
5 18
35 30

35

5 6 9
4 0
4 1
6 3
8 0
10 4
10 5

6

Hint

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