Problem Background

Xiao Zhang recently published a paper, and a mysterious person is going to award a scholarship to Xiao Zhang's college.

Problem Description

Xiao Zhang's college has $c$ students, with the $i$-th student having a score of $a_i$ and a desired scholarship amount of $b_i$.
From these $c$ students, $n$ students are to be selected to receive the scholarship. The mysterious person has a peculiar preference: he wants the median score of the students receiving the scholarship to be as high as possible, but at the same time, the total scholarship amount must not exceed $f$.

Input Format

The first line contains three integers, representing the number of students to be selected $n$, the total number of students $c$, and the maximum allowable total scholarship amount $f$. It is guaranteed that $n$ is an odd number.

From the second line to the $(c + 1)$-th line, each line contains two integers. The $(i + 1)$-th line represents the score $a_i$ and the scholarship amount $b_i$ for the $i$-th student.

Output Format

Output a single integer representing the answer. If it is impossible to meet the conditions of the mysterious person, output $-1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

35

Sample Input #2

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

Sample Output #2

6

Notes

Sample 1 Explanation

Selecting the three students with scores $5$, $35$, and $50$, the total scholarship amount is $18 + 30 + 21 = 69$.

Data Size and Constraints

• For $30\%$ of the data, it is guaranteed that $n \leq 10^3$, $c \leq 2 \times 10^3$.
• For $100\%$ of the data, 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$.

见题面 Input 部分

见题面 Output 部分