3395: 奖学金
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：1
题目描述
小张最近发表了一篇论文，有一个神秘人物要给小张学院发奖学金。
小张学院有 c 名学生，第 i 名学生的成绩为 ai，要获得的奖学金金额为bi。
要从这 cc 名学生中挑出 nn 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的成绩的中位数尽可能大，但同时，他们的奖学金总额不能超过 f。
要从这 cc 名学生中挑出 nn 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的成绩的中位数尽可能大，但同时，他们的奖学金总额不能超过 f。
输入格式
第一行有三个整数，分别表示要挑出的学生人数 n，学生总人数 c 和奖学金总额的最大值 f。
第 2 到第 (c+1) 行，每行两个整数，第 (i+1) 行的整数依次表示第 i 名学生的成绩 ai 和如果要给他发奖学金，则需要发的金额数 bi。
保证 3≤n≤105，n≤c≤2×105，0≤f≤2×109，0≤ai≤2×109，0≤bi≤105。
第 2 到第 (c+1) 行，每行两个整数，第 (i+1) 行的整数依次表示第 i 名学生的成绩 ai 和如果要给他发奖学金，则需要发的金额数 bi。
保证 3≤n≤105，n≤c≤2×105，0≤f≤2×109，0≤ai≤2×109，0≤bi≤105。
输出格式
输出一行一个整数表示答案。如果无法满足神秘人的条件，请输出 -1。
输入输出样例
输入 #1
3 5 70
30 25
50 21
20 20
5 18
35 30
输出 #1
35
输入 #2
5 6 9
4 0
4 1
6 3
8 0
10 4
10 5
输出 #2
6
说明/提示
样例 1 解释
选择成绩为 55，3535，5050 的三名同学，奖金总额为 18 + 30 + 21 = 6918+30+21=69。
输入输出样例
输入 #1
3 5 70
30 25
50 21
20 20
5 18
35 30
输出 #1
35
输入 #2
5 6 9
4 0
4 1
6 3
8 0
10 4
10 5
输出 #2
6
说明/提示
样例 1 解释
选择成绩为 55，3535，5050 的三名同学，奖金总额为 18 + 30 + 21 = 6918+30+21=69。
输入样例 复制
3 5 70
30 25
50 21
20 20
5 18
35 30输出样例 复制
35