题目描述

工程师 Nika 正在从一串测量值中挑选一组稳定的信号。给定一个长度为 $n$ 的数组

$$w_1,w_2,\ldots,w_n.$$

你需要从中选出一个长度为 $k$ 的子序列。设选中的下标为

$$1\le i_1<i_2<\cdots<i_k\le n.$$

选出的 $k$ 个元素会按原顺序围成一个环。这个环的稳定度由相邻两项之和的最大值决定，即

$$\max\left( w_{i_1}+w_{i_2}, w_{i_2}+w_{i_3}, \ldots, w_{i_{k-1}}+w_{i_k}, w_{i_k}+w_{i_1} \right).$$

请在所有长度为 $k$ 的子序列中，使上述最大值尽可能小，并输出这个最小可能值。

输入格式

第一行包含两个整数 $n,k$，分别表示数组长度和需要选择的子序列长度。

第二行包含 $n$ 个整数

$$w_1,w_2,\ldots,w_n.$$

输出格式

输出一行一个整数，表示所有长度为 $k$ 的子序列中，相邻环边权最大值的最小可能值。

数据范围

• $3\le k\le n\le 200000$；
• $1\le w_i\le 10^9$。

样例

输入

5 3
17 18 17 30 35

输出

35