← 返回题目列表

AtCoder · awc0025_c

C. 教室空调安装

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥负责学校的设施管理。学校有 N 教室,以及每个教室 i (1 \leq i \leq N)安装了一台旧空调。每个教室的空调都有劣化等级 D_i,其中老化程度越高意味着空调越旧并且性能越差。

这一次, M 新空调已到货。高桥可以选择 0 或更多以及 M 或更少的不同教室 N 教室,并将每个选定教室的旧空调更换为一台新空调。每个教室最多可更换一次,无需全部使用 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
  • 第一行包含一个整数 N 代表教室数量和一个整数 M 代表到达的新空调数量,以空格分隔。
  • 第二行包含整数 D_1, D_2, \ldots, D_N 代表每个教室的恶化程度,以空格分隔。

输出

在一行中打印更换后所有教室的最大恶化程度的最小可达到值。


示例输入 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