404024 - 新生录取

学院今年准备招N(N为奇数且1≤N≤19 999)个新生,报名有C人,每人的分数(1至2 000 000 000之间)和需要的学费补贴M(0≤M ≤100 000)不同,因为学院的学费很贵,不是所有新生都能承担得起的,而“基金会”能提供的经济补贴总额最多为F(0≤F≤2 000 000 000)。 请编程计算在招够N个新生且能支付得起学费的情况下的分数中位数最大,如果F的补贴无法招够N个新生,输出-1,否则输出中位数。 奇数个整数的中位数是排序时的中间值,例如集合{3,8,9,7,5}的中位数是7,因为正好两个值小于7并且两个值大于7。

输入

第一行为三个整数为N,C,F。随后C行,每行两个整数表示每个人的分数和学费补贴。

输出

如果满足条件输出最大的中位数,否则输出-1。

样例

输入

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

输出

35
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题