[USACO04MAR] Financial Aid

题目描述

有 $C$ 对数 $a_i,b_i$ （$a_i$互不相同）。

要求从中选 $N$ 对，使得所选对数满足 $\sum b_i \le F$ 的情况下 $a_i$ 中位数最大。

所谓中位数，就是排序后处在最中间的分数，比如3,8,9,7,5的中位数是7。

输入格式

第一行三个整数：$N \ C \ F \ \ (1 \le N \le 2 \times 10^4$，$N \le C \le 10^5$ ，$0 \le F \le 2 \times 10^9)$

下来 $C$ 行,每行有两个整数$a_i \ b_i \ (0 \le a_i \le 2\times 10^9,0 \le b_i \le 10^5 )$。

输出格式

一行一个整数，表示可以得到 $a_i$ 的最大中位数。

如果无法做到$\sum b_i \le F$，则输出 -1。

样例 #1

样例输入 #1

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

样例输出 #1

35

提示

选中 $a_i$ 为 5，35，50 的对数，中位数为 35，$\sum b_i = 18 + 30 + 21 = 69 \le 70$