Кевин Сан хочет переместить свою драгоценную коллекцию из n колокольчиков (конечно же коровьих) из Мухоглинска в Эксетер, а там — представьте себе! — на полях растёт не кукуруза, а настоящая трава. Для переезда ему надо упаковать все свои колокольчики в k коробок фиксированного размера. Чтобы коллекция не пострадала в ходе перевозки, Кевин не собирается класть в одну коробку более двух колокольчиков. Так как Кевин хочет минимизировать расходы, требуется найти минимальный размер коробок, которые он может использовать для упаковки всей своей коллекции.
Кевин — дотошный коллекционер, и он знает, что размер i-го колокольчика в его коллекции равен целому числу si. Кевин хранит колокольчики упорядоченными, а именно si - 1 ≤ si для всех i > 1. Также Кевин великолепно упаковывает вещи, поэтому он может поместить один или два колокольчика в коробку размера s тогда и только тогда, когда сумма их размеров не превышает s. Используя информацию о коллекции Кевина, найдите минимальное s, такое что Кевин сможет упаковать все свои n колокольчиков в k коробок размера s.
Выходные данные
Выведите единственное целое число — минимальное s, такое что Кевин сможет упаковать все свои n колокольчиков в k коробок размера s.
Примечание
В первом примере Кевину придётся упаковать оба колокольчика в одну коробку.
Во втором примере Кевин может упаковать колокольчики следующим образом: {2, 3}, {5} и {9}.
В третьем примере оптимальное решение следующее: {3, 5} и {7}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
2 5
|
7
|
|
2
|
4 3
2 3 5 9
|
9
|
|
3
|
3 2
3 5 7
|
8
|