#3372. [USACO 2004 Feb]Moo University -- Financial Aid 财政补助

[USACO 2004 Feb]Moo University -- Financial Aid 财政补助

题目描述

贝茜统计到人类拥有很多大学可以去就读,而奶牛们却一个大学也没有.为了解决这个问题,她和她的同伴们建立了一所奶牛大学 Moo 大学。为了防止笨牛入学,学校的创立者搞了一个奶牛智力测试(CSAT),它的分数在区间 [1,2×109][1, 2 × 10^9] 内。Moo 大学的学费很昂贵:不是所有奶牛都能负担。事实上,大多数奶牛需要一些财政帮助 aa。政府不会给奶牛任何资金,所以所有的资金都来自于学校有限的资金,资金总数为 FF。更糟的是,虽然有 CC 头奶牛报考,Moo大学却只能接受 NN 头奶牛(NN 为奇数)。贝茜既要让这 NN 头奶牛享受最大限度的教育资源,又要它们 CSAT 分数的中位数尽可能高。

这里说一下对于一个奇数个数组成的集合中中位数的概念.例如,集合 {3,8,9,7,5}\{3, 8, 9, 7, 5\} 的中位数是 77,因为有两个数小于 77,有两个数大于 77

给出每头奶牛的分数和所需的财政补贴数,可以接纳的奶牛数,补助的资金总数,求出中位数最大的可能值。

输入格式

11 行:三个用空格分开的整数 N,C,FN, C, F

22C+1C+1 行:每行有两个用空格隔开的整数。第一个数表示这头奶牛的CSAT分数;第二个整数表示这头奶牛所需的补助数额。

输出格式

仅一行,一个整数即最大的中位数可能值.如不存在输出 1-1

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

35

如果贝茜接收 CSAT 分数为 5,35,505, 35, 50 的奶牛,中位数为 3535。总的资金要求为 18+30+21=6918 + 30 + 21 = 69.

数据规模与约定

对于 100%100\% 的数据,0a1050 \leq a \leq 10^50F2×1090 \leq F \leq 2 × 10^91N<200001 \leq N < 20000NC105N \leq C \leq 10^5

题目来源

Green