No.507 ゲーム大会(チーム決め)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 40
作問者 : kzyKTkzyKT / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

2 ProblemId : 1164 / 出題時の順位表

問題文

$N$人が参加するゲームの大会で交流として、$2$人組を作り、$2$人の合計スコアで競い合うことにした。$($偶然人数が$2$で割り切れたので、余る人はいない$)$
上位$M$位以内には賞品が与えられる。
$M$位と同点が複数組いる場合そのすべての組も賞品を得ることができる。

$K$君は参加者を入念に調査したためそれぞれがどの程度スコアを取ることができるか知っている。
残りの人たちがどのように組んでも$K$君が確実に賞品を得られるようするには最低何点の人と組めば良いか求めよ。
もし、誰と組んでも賞品を得られない場合は$-1$を出力せよ。

入力

$N \ M$
$a_0$
$a_1$
$\dots$
$a_{N-1}$

$1$行目に$N$と$M$が空白区切りで与えられる。
$2$行目以降にそれぞれの人が取れるスコアが与えられる。
$a_0$が$K$君のスコアを表す。

入力はすべて整数で与えられる。
$2 \le N \le 10^5$($N$は偶数)
$1 \le M \le N/2$
$1 \le a_i \le 10^9$

出力

$K$君が組むべき人のスコアの最低点を出力せよ。
賞品を得られない場合は$-1$を出力せよ。

サンプル

サンプル1
入力
8 2
6
1
1
2
4
4
4
4
出力
2

例えば(6,2),(4,4),(4,4),(1,1)と組んだ場合、上から8点,8点,8点,2点となる。
2位の8点と同じなので3位まで賞品を得ることができる。

サンプル2
入力
6 1
1
1
4
5
1
4
出力
-1

$5$点の人と組んでも、$4$点の$2$人が組むと$1+5 \lt 4+4$で負けてしまう。

提出ページヘ