题目描述

人类可以选择很多大学，而奶牛们却没学可上。为解决这个问题，贝西和她的伙伴们创立了一所奶牛大学，取名为哞哞大学。

为了选拔优秀学生，她们发明了一种奶牛学术能力测试（简称 CSAT），这种测试的分数异常精确，每头奶牛的成绩可以用 $0$ 到 $2×10^9$ 之间的一个整数表示，而且可以保证每头奶牛的分数都不同。

哞哞大学的学费很贵，奶牛们表示负担不起，他们都各自申请了奖学金。政$$府并没有为奶牛准备奖学金，所有的预算都必须要从学校有限的助学基金中扣除（设基金总额为 $F$）。

哞哞大学有 $N$ 间宿舍，$N$ 是一个奇数，所以贝西只能接受 $N$ 头奶牛的申请，她发誓不会让入学的奶牛少于 $N$。此外，她希望新生的 CSAT 成绩表现优异，她以中位数来衡量新生的总体水平。所谓中位数，就是排序后处在最中间的分数，比如 $3,8,9,7,5$ 的中位数是 $7$。

今年，共有 $C$ 头奶牛申请入学，给定每头奶牛的 CSAT 成绩和申请的奖学金数目，以及学校可赞助的总额，确定贝西接受哪些奶牛的申请才可以使成绩的中位数达到最大。

输入格式

第一行：三个用空格分开的整数：$N,C$ 和 $F$ $(1 \le N \le 19999$,$N \le C \le 10^5$,$0 \le F \le 2 × 10^9)$。

第二行到 $C + 1$ 行：每行有两个用空格分开的整数。第一个数是这头奶牛的 CSAT 成绩，第二个数是这头奶牛需要的奖学金 $Q_i$ $(0 \le Q_i \le 10^5)$。

输出格式

第一行：一个整数，表示贝西可以得到的最大中位数，如果现有基金不够资助任何 $N$ 头奶牛，则输出 $-1$。

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

35

提示

贝西接受 CSAT 分数为 $5,35,50$ 的奶牛的申请，中位数为 $35$，需支付的奖学金总额为 $18 + 30 + 21 = 69$。