该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

RD要搬家了，她要打包好自己的收藏品。（主要是奖杯）

现在有n件物品需要搬运，为了防止碰坏，RD只会把最多两件物品放在同一个箱子里。

若两件物品体积之和不超过箱子的体积，就可以放进去。

RD准备订购至多K只相同体积的箱子，为了减少花费，请计算箱子的最小体积。

输入格式

第一行，两个整数，n,k.(1≤n≤2•k≤100 000)

第二行，n个整数{$v_i$}，表示n个物品的体积。$1≤v_i≤1 000 000$

RD保持着良好的整理习惯，因此数列{v}是单调不减的。

输出格式

一个整数表示箱子的最小体积。

样例

输入1

2 1
2 5

输出1

7

输入2

4 3
2 3 5 9

输出2

9

输入3

3 2
3 5 7

输出3

8

数据范围与提示

50%:1≤n≤2•k≤1 000,$1≤v_i≤10 000$