nocLyt

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

我们的家乡在山东省内向来以人口众多,经济贫穷闻名...T_T
 
2036年的天,全宇宙超级大富豪秦川先生坐在自己的私家航天飞机里俯瞰大地,突然觉得自己应该为家乡做点什么。
 
嗯,于是他决定节食一天,把自己省下来的一天的餐费 F(0<F<=10^9)用来捐助自己家乡的教育事业! Orz真的是太伟大了!
现在已知有C (C<=10^6)个需要资助的学生,每个学生有两条信息,成绩si(0<=si<=100)和需要的资金vi(0<vi<= 10^4)。
作为一个睿智的超级富豪,他觉得自己的钱要用的让自己放心。然后他告诉他的手下,他要恰好资助N个学生(N<10^5,即这N个学生需要的总资金<=F)。
为了显示自己的睿智,超级富豪秦川要使这选定的N个学生的成绩的中位数最大,如果有多种满足条件的情况,还要使剩下的钱最多。因为秦川神还要去资助一下中国教育部。。。
 
作为秦川的手下,都一把年纪还没有妹子的nocLyt表示压力很大T_T...。nocLyt希望能好好的完成这个任务,这样秦川神就能奖赏妹子一枚了。。。
好心的你能不能帮帮nocLyt呢?

Input

第一行三个正整数, C N F
接下来是 C行, 从第2行到第C+1行, 每行有两个正整数 si, vi。
数据保证 N为奇数且 0<N<= C;

Output

输出仅一行,两个正整数,即 N个学生的成绩的中位数的最大值 和 剩下的钱数。

Sample Input

6 3 7000
30 2500
50 2100
20 2000
5 1800
35 3000
35 2999

Sample Output

35 101

Hint

资助 第2,4,5 三个学生,中位数 35,还剩下 100。
但是 资助 第2,4,6 三个学生,中位数 35,还剩下 101, 显然更优。
最后题目保证, 对于每组数据F足是足够大,必然存在解。

Source

山东农业大学