新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:30000KB
問題 
Bessieは、人間のための大学は数多く存在するのに、牛のための大学が存在しないことに気付きました。この問題を解決するために、彼女と仲間の牛たちはThe University of Wisconsin-Farmside, つまり"Moo U"という大学を作りました。
平均より劣る牛たちは入学させたくないので、創設者はCow Scholastic Aptitude Test（CSAT）と呼ばれる非常に精密な入学試験を作成しました。このテストの点数の範囲は 1..2,000,000,000 です。
Moo Uの学費はとても高く、払う余裕がない子牛もいます。実際に、ほとんどの子牛がいくらかの資金援助 aid（0 <= aid <= 100,000）を必要としています。政府は補助金を出資してくれないので、限られた大学の基金F（0 <= F <= 2,000,000,000）から資金援助を行わなくてはなりません。
さらに悪いことに、Moo Uにはある奇数N（1 <= N <= 19,999）匹分の教室しかいないのに対して、志願した牛はC（N <= C <= 100,000）匹います。Bessieは教育の機会を最大化したいので、ちょうどN匹の子牛を入学させたいと思っています。彼女は合格した子牛たちのCSATの中央値を、できる限り高くしたいとも考えています。
大きさが奇数である整数列の中央値とは、数列をソートした時に中央に来る値の事を言います。たとえば、数列{3, 8, 9, 7, 5} の中央値は7で、数列に7より大きい値と7より小さい値がちょうど2つずつ含まれるためそうなります。
志願した子牛のCSATのスコアと必要な資金援助額、合格させる子牛の総数、Bessieが持つ資金援助のための総額が与えられるとき、最適な選び方をした場合にBessieが得られる最大のCSATのスコアの中央値を求めてください。
入力
1行: スペースで区切られた3つの整数 N, C, F
2～C+1行: スペースで区切られた2つの整数 i番目の子牛のCSATのスコア, i番目の子牛の必要な資金援助額
出力
1行: 1つの整数 Bessieが得られる最大のCSATのスコアの中央値
もし資金FでN匹の子牛を入学させることができなければ、-1を出力せよ。
入力の例
3 5 70 30 25 50 21 20 20 5 18 35 30
出力の例
35
ヒント
BessieがCSATのスコアが5, 35, 50である3匹を合格させたとき中央値は35になる。合計の資金援助額は18 + 30 + 21 = 69 <= 70 となる。
出典
USACO 2004 March Green
