题目描述

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

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

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

输入格式

第 $1$ 行：三个用空格分开的整数 $N, C, F$。

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

输出格式

仅一行，一个整数即最大的中位数可能值．如不存在输出 $-1$。

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

35

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

数据规模与约定

对于 $100\%$ 的数据，$0 \leq a \leq 10^5$，$0 \leq F \leq 2 × 10^9$，$1 \leq N < 20000$，$N \leq C \leq 10^5$。

题目来源

Green