Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

B. Коровам - колокольчиков!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин Сан хочет переместить свою драгоценную коллекцию из n колокольчиков (конечно же коровьих) из Мухоглинска в Эксетер, а там — представьте себе! — на полях растёт не кукуруза, а настоящая трава. Для переезда ему надо упаковать все свои колокольчики в k коробок фиксированного размера. Чтобы коллекция не пострадала в ходе перевозки, Кевин не собирается класть в одну коробку более двух колокольчиков. Так как Кевин хочет минимизировать расходы, требуется найти минимальный размер коробок, которые он может использовать для упаковки всей своей коллекции.

Кевин — дотошный коллекционер, и он знает, что размер i-го колокольчика в его коллекции равен целому числу si. Кевин хранит колокольчики упорядоченными, а именно si - 1 ≤ si для всех i > 1. Также Кевин великолепно упаковывает вещи, поэтому он может поместить один или два колокольчика в коробку размера s тогда и только тогда, когда сумма их размеров не превышает s. Используя информацию о коллекции Кевина, найдите минимальное s, такое что Кевин сможет упаковать все свои n колокольчиков в k коробок размера s.

Входные данные

В первой строке входных данных находятся два числа n и k (1 ≤ n ≤ 2·k ≤ 100 000), обозначающие количество колокольчиков и количество коробок соответственно.

В следующей строке записано n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 1 000 000) — размеры колокольчиков в коллекции Кевина. Гарантируется, что si следуют в порядке неубывания.

Выходные данные

Выведите единственное целое число — минимальное s, такое что Кевин сможет упаковать все свои n колокольчиков в k коробок размера s.

Примеры
Входные данные
2 1
2 5
Выходные данные
7
Входные данные
4 3
2 3 5 9
Выходные данные
9
Входные данные
3 2
3 5 7
Выходные данные
8
Примечание

В первом примере Кевину придётся упаковать оба колокольчика в одну коробку.

Во втором примере Кевин может упаковать колокольчики следующим образом: {2, 3}, {5} и {9}.

В третьем примере оптимальное решение следующее: {3, 5} и {7}.