[USACO04MAR] Financial Aid

题目描述

人类可以选择很多大学,而奶牛们却没学可上。为解决这个问题,贝西和她的伙伴们创立了一所奶牛大学,取名为哞哞大学。 为了选拔优秀学生,她们发明了一种奶牛学术能力测试(简称 CSAT) ,这种测试的分数异常精确,每头奶牛的成绩可以用$0$到$2×10^9$之间的一个整数表示,而且可以保证每头奶牛的分数都不同。 哞哞大学的学费很贵,奶牛们表示负担不起,他们都各自申请了奖学金。政府并没有为奶牛准备奖学金,所有的预算都必须要从学校有限的助学基金中扣除(设基金总额为F)。 哞哞大学有N间宿舍,N是一个奇数,所以贝西只能接受N头奶牛的申请,她发誓不会让入学的奶牛少于N。此外,她希望新生的 CSAT 成绩表现优异,她以中位数来衡量新生的总体水平。所谓中位数,就是排序后处在最中间的分数,比如3,8,9,7,5的中位数是7。 今年,共有C头奶牛申请入学,给定每头奶牛的 CSAT 成绩和申请的奖学金数目,以及学校可赞助的总额,确定贝西接受哪些奶牛的申请才可以使成绩的中位数达到最大。

输入输出格式

输入格式


第一行:三个用空格分开的整数:$N$,$C$和$F$。$1 ≤ N ≤ 19999$,$N ≤ C ≤ 10^5$ ,$0 ≤ F ≤ 2 × 10^9$ 第二行到$C + 1$行:每行有两个用空格分开的整数。第一个数是这头奶牛的 CSAT 成绩,第二个数是这头奶牛需要的奖学金$Q_i$ ,$0 ≤ Q_i ≤ 10^5 $。

输出格式


第一行:一个整数,表示贝西可以得到的最大中位数,如果现有基金不够资助任何N头奶牛,则输出-1。

输入输出样例

输入样例 #1

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

输出样例 #1

35

说明

贝西接受 CSAT 分数为 5,35,50 的奶牛的申请,中位数为 35,需支付的奖学金总额为18 + 30 + 21 = 69