C - 教室のエアコン配備 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は学校の設備管理を担当しています。学校には N 個の教室があり、それぞれの教室 i（1 \leq i \leq N）には古いエアコンが 1 台設置されています。各教室のエアコンには老朽度 D_i が定められており、老朽度が高いほどエアコンが古く性能が悪いことを意味します。

今回、新しいエアコンが M 台届きました。高橋君は、N 個の教室の中から 0 個以上 M 個以下の相異なる教室を選び、選んだ各教室の古いエアコンを新しいエアコン 1 台と交換することができます。各教室に対して交換できるのは最大 1 回であり、届いた M 台すべてを使い切る必要はありません。交換を行った教室の老朽度は 0 になり、交換を行わなかった教室の老朽度は元の D_i のまま変わりません。

高橋君は、交換する教室をうまく選ぶことで、交換後における全教室の老朽度の最大値をできるだけ小さくしたいと考えています。この最大値として達成可能な最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N
  • 0 \leq D_i \leq 10^9
  • 入力はすべて整数である

入力

N M
D_1 D_2 \ldots D_N
  • 1 行目には、教室の数を表す整数 N と、届いた新しいエアコンの台数を表す整数 M が、空白区切りで与えられる。
  • 2 行目には、各教室の老朽度を表す整数 D_1, D_2, \ldots, D_N が、空白区切りで与えられる。

出力

交換後における全教室の老朽度の最大値として達成可能な最小値を 1 行で出力せよ。

入力例 1

5 2
3 1 4 1 5

出力例 1

3

入力例 2

7 7
10 20 30 40 50 60 70

出力例 2

0

入力例 3

10 3
100 200 300 400 500 600 700 800 900 1000000000

出力例 3

700

Score : 300 pts

Problem Statement

Takahashi is in charge of facility management at a school. The school has N classrooms, and each classroom i (1 \leq i \leq N) has one old air conditioner installed. Each classroom's air conditioner has a deterioration level D_i, where a higher deterioration level means the air conditioner is older and has worse performance.

This time, M new air conditioners have arrived. Takahashi can choose 0 or more and M or fewer distinct classrooms from the N classrooms, and replace the old air conditioner in each chosen classroom with one new air conditioner. Each classroom can be replaced at most once, and it is not necessary to use all M new air conditioners. The deterioration level of a classroom where a replacement was made becomes 0, while the deterioration level of a classroom where no replacement was made remains at its original value D_i.

Takahashi wants to choose the classrooms for replacement wisely so as to minimize the maximum deterioration level among all classrooms after the replacements. Find the minimum achievable value of this maximum.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N
  • 0 \leq D_i \leq 10^9
  • All input values are integers

Input

N M
D_1 D_2 \ldots D_N
  • The first line contains an integer N representing the number of classrooms and an integer M representing the number of new air conditioners that arrived, separated by a space.
  • The second line contains integers D_1, D_2, \ldots, D_N representing the deterioration level of each classroom, separated by spaces.

Output

Print in one line the minimum achievable value of the maximum deterioration level among all classrooms after the replacements.

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

3

Sample Input 2

7 7
10 20 30 40 50 60 70

Sample Output 2

0

Sample Input 3

10 3
100 200 300 400 500 600 700 800 900 1000000000

Sample Output 3

700