#P3372. [Usaco2004 Feb]Moo University -- Financial Aid 财政补助
[Usaco2004 Feb]Moo University -- Financial Aid 财政补助
[USACO 2004 Mar] Moo University - Financial Aid 财政补助
题目描述
贝茜和伙伴们创建了 Moo 大学,设计了奶牛学术能力测试 CSAT 来招收学生。大学学费昂贵,有些奶牛需要学校提供补助。学校可用的补助预算为 。共有 头奶牛申请入学,学校必须恰好录取 头,其中 为奇数。
选出的 头奶牛的 CSAT 成绩从小到大排列,排在正中间的成绩就是中位数。例如, 的中位数是 。学校希望在录取者所需补助的总额不超过预算的前提下,让成绩中位数尽可能高。
输入格式
从标准输入读入。第一行是三个整数 。接下来 行,每行两个整数,依次给出一头奶牛的 CSAT 成绩和她所需的补助额 。
输出格式
向标准输出输出一行一个整数,表示可能达到的最大中位数。如果预算无法录取恰好 头奶牛,输出 。
3 5 70
30 25
50 21
20 20
5 18
35 30
35
样例解释
录取成绩为 的奶牛,所需补助共 ,不超预算。中位数为 。
数据范围与约定
为奇数,,,,。CSAT 成绩在 到 之间。