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

附加文件

题目描述

N 个物品，编号为 1 ~ N。物品 i 的价值是 Wi，体积是 Vi。

有一个背包，容量为 C。

现在要将恰好 K 个物品装入背包，要求装入背包的物品的体积之和不能超过 C，且这些物品的价值的中位数（记为 M）尽可能大。

请你求出 M 的最大值。

输入格式

第一行：三个整数：K，N，C。

接下来 N 行：每行两个整数 Wi，Vi。

输出格式

一个整数，表示 M 的最大值。如果没有合法方案，输出 -1

样例输入

3 5 100
30 30
50 50
20 20
10 10
40 60

样例输出

30

数据范围

$0 < K < 2 × 10^4 且 K 为奇数$ ，$K ≤ N ≤ 10^5$ ，$0 ≤ W_i, C ≤ 2 × 10^9$ ，$0 ≤ V_i ≤ 10^5$