题目描述

有一个容量为 $M$ 的背包，以及 $N$ 个物品，每个物品都有它的体积 $V_i$ 和价值 $W_i$. 现要选出 $K$ 个物品装入背包，要求这些物品的体积之和不超过 $M$，在此前提下，这些物品的价值的中位数越大，这个背包就越优. 求最优背包中的物品价值的中位数.

输入格式

输入第一行包括三个由空格分隔的正整数 $N$，$M$，$K$.

接下来 $N$ 行，每行两个由空格分隔的正整数 $V_i$，$W_i$.

输出格式

输出仅一行，即最优背包中的物品价值的中位数. 如果无论哪 $K$ 个物品的体积之和都会超过容量 $M$，输出-1.

样例输入

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

样例输出

35

样例1说明

将第2,4,5个物品装入背包，总体积为69，价值的中位数为35，为最优背包.

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$