题目描述

小飞侠是一名星际探险家，他在一处古代遗迹中发现了 $N$ 块能量晶石。每块晶石都有一个能量值 $A_i$。为了启动遗迹的传送门，小蓝需要将这些晶石两两配对，总共需要组成 $K$ 对（即消耗 $2K$ 块晶石，剩下的晶石不使用）。

每一对晶石产生的“共鸣强度”等于这两块晶石能量值之和。传送门的稳定性取决于这 $K$ 对晶石中 共鸣强度最低 的那一对。我们定义第 $i$ 对晶石的能量分别为 $x_i$ 和 $y_i$，则该方案的稳定性 $S$ 为：

小飞侠希望传送门尽可能稳定。请你帮他找出一种配对方案，使得这个最小的共鸣强度尽可能大。你的任务是计算出这个 $S$ 的最大可能值。

输入格式

输入包含两行：第一行包含两个整数 $N$ 和 $K$，分别表示晶石的总数和需要组成的对数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每块晶石的能量值。

输出格式

输出一个整数，表示 $K$ 对晶石中，最小共鸣强度的最大可能值。

数据范围

对于30%的数据

$1 \le N \le 1000$

$1 \le K \le \lfloor N/2 \rfloor$

$1 \le A_i \le 10^6$

对于80%的数据

$1 \le N \le 5*10^4$

$1 \le K \le \lfloor N/2 \rfloor$

$1 \le A_i \le 10^9$

对于100%的数据

$1 \le N \le 10^5$

$1 \le K \le \lfloor N/2 \rfloor$

$1 \le A_i \le 10^9$

输入样例:

6 2
1 5 9 2 6 8

输出样例：

14

样例解释：

将能量值排序为：$1,2,5,6,8,9。$ 选择 $5、6、8、9$四块晶石，并配成 $(5+9) 和 (6+8)$，两对的共鸣强度均为 $14$，最小值为$14$。

无法构造最小共鸣强度大于$14$的方案，因此答案为 $14$。