一般贪心

Description

Kevin Sun wants to move his precious collection of n cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into k boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection.

Kevin is a meticulous cowbell collector and knows that the size of his i-th (1 ≤ i ≤ n) cowbell is an integer s_i. In fact, he keeps his cowbells sorted by size, so s_i - 1 ≤ s_i for any i > 1. Also an expert packer, Kevin can fit one or two cowbells into a box of size s if and only if the sum of their sizes does not exceed s. Given this information, help Kevin determine the smallest s for which it is possible to put all of his cowbells into k boxes of size s.

Input

The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 2·k ≤ 100 000), denoting the number of cowbells and the number of boxes, respectively.

The next line contains n space-separated integers s₁, s₂, ..., s_n (1 ≤ s₁ ≤ s₂ ≤ ... ≤ s_n ≤ 1 000 000), the sizes of Kevin's cowbells. It is guaranteed that the sizes s_i are given in non-decreasing order.

Output

Print a single integer, the smallest s for which it is possible for Kevin to put all of his cowbells into k boxes of size s.

Sample Input

Input

2 1
2 5

Output

Input

4 3
2 3 5 9

Output

Input

3 2
3 5 7

Output

Sample Output

Hint

In the first sample, Kevin must pack his two cowbells into the same box.

In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.

In the third sample, the optimal solution is {3, 5} and {7}.

题意大概是N个东西放到K个箱子，可以两个放到一起，求最小的箱子体积（没个箱子都一样大）

此为一道贪心，然而直接思考可能太抽象，不妨把想象过程，在思想中模拟（神探夏洛克的的思维宫殿),这时就会发现只是一道水题#.#;

我们先从大的开始放到箱子里，直到放满，剩下的小的再往里放，最小的放到能相对来说最大的，

贪心就是找到一种放的方式先开始，然后开始规划改变称最优的；

这里给一下代码

#include<stdio.h>
#include<algorithm>
using namespace std;
long long n,k,s[100005],maxs;
int main()
{
    scanf("%lld%lld",&n,&k);
    for(long long i=0; i<n; i++)
        scanf("%lld",&s[i]);
    maxs=s[n-1];
    for(long long i=0; i<n-k; i++)
        maxs=max(maxs,s[i]+s[(n-k)*2-i-1]);

    printf("%lld
",maxs);
    return 0;
}