题目背景

小张最近发表了一篇论文，有一个神秘人物要给小张学院发奖学金。

题目描述

小张学院有 $c$ 名学生，第 $i$ 名学生的成绩为 $a_i$，要获得的奖学金金额为 $b_i$。
要从这 $c$ 名学生中挑出 $n$ 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的成绩的中位数尽可能大，但同时，他们的奖学金总额不能超过 $f$。

输入格式

第一行有三个整数，分别表示要挑出的学生人数 $n$，学生总人数 $c$ 和奖学金总额的最大值 $f$，保证 $n$ 为奇数。

第 $2$ 到第 $(c + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数依次表示第 $i$ 名学生的成绩 $a_i$ 和如果要给他发奖学金，则需要发的金额数 $b_i$。

输出格式

输出一行一个整数表示答案。如果无法满足神秘人的条件，请输出 $-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

提示

样例 1 解释

选择成绩为 $5$，$35$，$50$ 的三名同学，奖金总额为 $18 + 30 + 21 = 69$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \leq 10^3$，$c \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $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$。