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_1, s_2, ..., s_{n} (1 ≤ s_1 ≤ s_2 ≤ ... ≤ 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.


-----Examples-----
Input
2 1
2 5

Output
7

Input
4 3
2 3 5 9

Output
9

Input
3 2
3 5 7

Output
8



-----Note-----

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}.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int,input().split()))
L = list(map(int,input().split()))
i = 0
p = 0
z = 1
R = [0 for _ in range(k)]
while i<n:
    R[p] += L[n-1-i]
    p = p + z
    i+=1
    if p == k or p == -1:
        z = z*(-1)
        if p == k:
            p = p - 1
        else:
            p = p + 1
print(max(R))



n, k = map(int, input().split(" "))
s = list(map(int, input().split(" ")))
s.sort()
result = s[len(s) - 1]
while k*2 > n:
	n -= 1
	k -= 1
if n > 0:
	for i in range(int(n/2)):
		result = max( result, s[i] + s[n-1-i])
print(result)

n,k = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
l = max(a)-1
r = 100000000001

def check(s):
	count = 0
	l = 0
	r = n-1
	while l<=r:
		if l!=r and a[l]+a[r]<=s:
			count +=1
			l+=1
			r-=1
		else:
			r-=1
			count +=1
	if count <= k:
		return True
	else:
		return False

while (r-l>1):
	m = (r+l+1)//2
	#print(l,m,r)
	if check(m):
		r = m
	else:
		l = m
	
print(r)



n, k = list(map(int, input().split(" ")))
l = list(map(int, input().split(" ")))

li = []

for i in range((n-k-1)+1):
    li.append(l[i] + l[2*(n-k-1)+1 - i])

if(len(li) == 0):
    print(l[n-1])
else:        
    print(max(max(li), l[n-1]))


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))

t = k - (2*k - n)
res = 0
for i in range(t):
	res = max ( res, a[i] + a[2*t-1-i])
res = max(res, a[n-1])
print (res) 



import sys

line1 = sys.stdin.readline().split()
n = int(line1[0])
k = int(line1[1])

s = sys.stdin.readline().split()
s = [int(x) for x in s]

if n == 1:
    print(s[0])
else:
    pairs = s[:(2*n-2*k)]

    pair_sums = []
    for i in range(int(len(pairs)/2)):
        pair_sums.append(pairs[i]+pairs[-i-1])

    #print(pairs)
    #print(pair_sums)
    if len(pair_sums)>0:
        pmax = max(pair_sums)
    else:
        pmax = 0
    singles = s[-(2*k-n):]
    #print(singles)
    if len(singles)>0:
        smax = max(singles)
    else:
        smax = 0
    print(max(pmax,smax))



n,k = map(int,input().split())
S = list(map(int,input().split()))

t = n - k
m = 0
for i in range(n):
    if i < t:
        s = S[i] + S[2*t - 1 - i]
    elif i < 2*t:
        continue
    else:
        s = S[i]
    if s > m:
        m = s
print(m)

import math
n, k = map(int, input().split())
data = list(map(int, input().split()))
colvo_1_cor = k * 2 - n
colvo_2_cor = k - colvo_1_cor
answer = []
if colvo_1_cor > n:
    colvo_1_cor = n
for i in range(colvo_1_cor):
    answer.append(data[-1])
    data.pop()
if len(data) > 0:
    index1 = 0
    index2 = len(data) - 1    
    while index1 != len(data) // 2 + 1:
        answer.append(data[index1] + data[index2])
        index1 += 1
        index2 -= 1
print(max(answer))

n, k = list(map(int, input().split()))
s = list(map(int, input().split()))
maxi = 0
pos = n - 1
if n == 1:
    print(s[0])
else:
 if k >= n:
     print(s[-1])
 else:
  while 2 * (k - 1) >= (n - 1):
      maxi = max(maxi, s[pos])
      pos -= 1
      k -= 1
      n -= 1
  posq = 0
  while pos - posq >= 1:
      maxi = max(maxi, s[posq] + s[pos])
      pos -= 1
      posq += 1
  if pos == posq:
      maxi = max(maxi, s[pos])
  print(maxi)


import math

def can_pack(m, b):
    nonlocal n, k
    cnt = 0
    if b[-1] > m:
        return False
    p1 = 0
    p2 = n - 1
    while p1 < p2:
        if b[p2] + b[p1] <= m:
            p1 += 1
            p2 -= 1
        else:
            p2 -= 1
        cnt += 1
    if p1 == p2:
        cnt += 1
    return cnt <= k


n, k = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
l = 0
r = 10 ** 9
while l != r - 1:
    m = (l + r) // 2
    if not can_pack(m, b):
        l = m
    else:
        r = m
print(r)

n, k = list(map(int, input().split()))
sizes = list(map(int, input().split()))

def solve(n, k, sizes):
    if k >= n:
        return max(sizes)
    head = sizes[:n - k]
    tail = sizes[n - k:]
    for i, h in enumerate(head[::-1]):
        tail[i] += h
    return max(tail)

print(solve(n, k, sizes))


n,k = input().split()
n=int(n)
k=int(k)
s=input().split()
for i in range(n):
    s[i]=int(s[i])
    #print(i,"",end="")
r=(n-k)*2
m=s[-1]
i=0
if(k>=n):
    print(m)
else:
    while(i<r):
        x=s[i]+s[r-i-1]
        #print(i,r-i)
        if(m<x):
            m=x
        i+=1
    print(m)


n, k = map(int, input().split())
s = list(map(int, input().split()))

p1 = []
p2 = []

if n <= k:
    print(max(s))
else:
    for i in range(n - k):
        p1.append(s[i] + s[2 * (n - k) - i - 1])
        p2.append(s[2 * i] + s[2 * i + 1])
    
    for i in range(n - k + 1, n):
        p1.append(s[i])
        p2.append(s[i])
    
    print(min(max(p1), max(p2)))

"""
Codeforces Round #334 (Div. 2)

Problem 604 B. More Cowbell

@author yamaton
@date 2015-12-01
"""

import itertools as it
import functools
import operator
import collections
import math
import sys


def solve(xs, n, k):
    if k >= n:
        return max(xs)
    ys1 = xs[:(n - k)]
    ys2 = xs[(n - k) : 2*(n - k)]
    maxval = max(a + b for (a, b) in zip(ys1, ys2[::-1]))
    return max(maxval, xs[-1])

# def pp(*args, **kwargs):
#     return print(*args, file=sys.stderr, **kwargs)


def main():
    n, k = list(map(int, input().split()))
    xs = [int(c) for c in input().split()]
    assert len(xs) == n
    result = solve(xs, n, k)
    print(result)


def __starting_point():
    main()

__starting_point()

"""
Codeforces Round #334 (Div. 2)

Problem 604 B. More Cowbell

@author yamaton
@date 2015-12-01
"""

import itertools as it
import functools
import operator
import collections
import math
import sys


def solve(xs, n, k):
    # assert xs is sorted
    if k >= n:
        return xs[-1]
    ys1 = it.islice(xs, n - k)
    ys2 = it.islice(xs, n - k, 2*(n - k))
    ys2rev = reversed(list(ys2))
    maxval = max(a + b for (a, b) in zip(ys1, ys2rev))
    return max(maxval, xs[-1])


# def pp(*args, **kwargs):
#     return print(*args, file=sys.stderr, **kwargs)


def main():
    n, k = list(map(int, input().split()))
    xs = [int(c) for c in input().split()]
    assert len(xs) == n
    result = solve(xs, n, k)
    print(result)


def __starting_point():
    main()

__starting_point()

def main():
	n, k = (map(int, input().split()))
	s = list(map(int, input().split()))

	minSize = s[n - 1]
	
	if n <= k:
		print(minSize)
		return

	
	i = 0
	total = n - 1
	while 2 * k > n :
		n, k = n - 1, k - 1
	for i in range(k):
		minSize = max(minSize, s[i] + s[n - i - 1])

	print(minSize)



def __starting_point():
	main()
__starting_point()

a, b = list(map(int, input().split(' ')))
x = list(map(int, input().split(' ')))

def f(num):
    lo = 0
    hi = a-1
    ct = 0
    while lo <= hi:
        if lo == hi:
            ct += 1
            break
        if x[lo] + x[hi] <= num:
            lo+=1
            hi-=1
        else:
            hi-=1
        ct+=1
    return ct

lo = max(x)
hi = 100000000
while lo < hi:
    mid = (lo + hi) // 2
    if f(mid) > b:
        lo = mid + 1
    else:
        hi = mid

print(lo)


__author__ = 'heckboy'
#!/usr/bin/env python
n, k = map(int,input().split())
L = list(map(int,input().split()))
i = 0
p = 0
z = 1
R = [0 for _ in range(k)]
while i<n:
    R[p] += L[n-1-i]
    p = p + z
    i+=1
    if p == k or p == -1:
        z = z*(-1)
        if p == k:
            p = p - 1
        else:
            p = p + 1
print(max(R))

n,k=map(int,input().split())
a=list(map(int,input().split()))
d=n-k
m=0
for i in range(d):
    m=max(m,a[i]+a[2*d-i-1])
print(max(m,a[-1]))

n, k = list(map(int, input().split(" ")))
thing = input()
thing = thing.split(" ")
balls = []
for t in thing:
    balls += [int(t)]

if n<=k:
    m = max(balls)
else:
    squeeze = n-k

    m=0

    for i in range (squeeze):
        current = balls[i] + balls[2*squeeze-1-i]
        m = max(current, m)

    m = max(balls[n-1], m)

print (m)


#!/usr/bin/env python3
# 604B_cowbell.py - Codeforces.com/problemset/problem/604/B by Sergey 2015

import unittest
import sys

###############################################################################
# Cowbell Class (Main Program)
###############################################################################


class Cowbell:
    """ Cowbell representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n, self.k] = list(map(int, uinput().split()))

        # Reading a single line of multiple elements
        self.nums = list(map(int, uinput().split()))

    def calculate(self):
        """ Main calcualtion function of the class """

        b = self.nums[self.n-self.k:]
        for i in range(self.n-self.k):
            b[i] += self.nums[self.n-self.k-1-i]
        result = max(b)

        return str(result)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Cowbell class testing """

        # Constructor test
        test = "2 1\n2 5"
        d = Cowbell(test)
        self.assertEqual(d.n, 2)
        self.assertEqual(d.k, 1)
        self.assertEqual(d.nums, [2, 5])

        # Sample test
        self.assertEqual(Cowbell(test).calculate(), "7")

        # Sample test
        test = "4 3\n2 3 5 9"
        self.assertEqual(Cowbell(test).calculate(), "9")

        # Sample test
        test = "3 2\n3 5 7"
        self.assertEqual(Cowbell(test).calculate(), "8")

        # My tests
        test = ""
        # self.assertEqual(Cowbell(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + " " + str(nmax) + "\n"
        numnums = [str(i) + " " + str(i+1) for i in range(nmax)]
        test += "\n".join(numnums) + "\n"
        nums = [random.randint(1, 10000) for i in range(nmax)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Cowbell(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Cowbell().calculate())

__starting_point()

n, k = map(int, input().split(" "))
s = list(map(int, input().split(" ")))
result = s[-1]
while k*2 > n:
    n -= 1
    k -= 1
if n > 0:
    for i in range(int(n/2)):
        result = max( result, s[i] + s[n-1-i])
print(result)

num_cows, num_boxes = list(map(int, input().split()))
cows = list(map(int, input().split()))
need = cows[-1]
limit = 2 * (num_cows - num_boxes)
for left in range(limit):
    right = limit - 1 - left
    if right < left:
        break
    need = max(need, cows[left] + cows[right])
print(need)


n, k = map(int, input().split())
size = list(map(int, input().split()))
l = size[-1] - 1
r = size[-1] * 2
while r - l > 1:
    m = (r + l) // 2
    x1, x2 = 0, len(size) - 1
    cnt = 0
    while x1 <= x2:
        if size[x1] + size[x2] <= m:
            x1 += 1
            x2 -= 1
        else:
            x2 -= 1
        cnt += 1
    if cnt <= k:
        r = m
    else:
        l = m
print(r)

def __starting_point():
    n, k = list(map(int, input().split()))
    s_list = list(map(int, input().split()))

    a_list = s_list[:n - min(n, 2 * k - n)]
    b_list = reversed(a_list)
    c_list = [a + b for a, b in zip(a_list, b_list)]
    print(max(max(c_list or [0]), max(s_list)))

__starting_point()