该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

题目描述

U 大学有 $N$ 名职员，编号为 $1$ ∼ $N$。

每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1 ≤ i ≤ N$。

现在要召开一场周年庆宴舞会。

主办方希望邀请 $K$ ($K$ 是一个奇数)名职员去参加舞会。

邀请职员 $i$ 需要支付 $C_i$ 的费用。

主办方的资金额度为 $M$。

主办方希望邀请的 $K$ 名职员的“快乐指数”的中位数最大，求这个最大值。

输入格式

第一行包含三个正整数 $K$ 、 $N$ 、 $M$。

接下来 $N$ 行，每行两个整数 $H_i$ , $C_i$ ,依次表示职员 $i$ 的快乐指数、他被邀请需要支付的费用。

输出格式

一个整数，表示答案。如果主办方资金不够，则输出 -1

样例输入

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

样例输出

35

数据范围

$0 < K < 20000$，$K ≤ N ≤ 10^5$ ，$0 ≤ M, H_i ≤ 2 × 10^9$，$0 ≤ C_i ≤ 10^5$

数据保证 $K$ 是奇数