Только что закончилась Берлядская межвузовская олимпиада. Монокарп и Поликарп, как члены жюри, собираются провести разбор. К сожалению, время у них ограничено, так как надо закончить до церемонии закрытия.
В соревновании было \(n\) задач. Задачи пронумерованы от \(1\) до \(n\). Разбор \(i\)-й задачи занимает \(a_i\) минут. Монокарп и Поликарп планируют разобрать ровно \(k\) из них.
Разбор проходит следующим образом. Перед ними лежит весь проблемсет из \(n\) задач. Они убирают \(n - k\) из них, не изменяя порядок оставшихся \(k\) задач. Затем Монокарп забирает себе какой-то префикс из этих \(k\) задач (возможно, пустой или все задачи). Поликарп забирает себе оставшийся суффикс. После этого они идут в разные комнаты и проводят разборы для своих задач параллельно. Так что разбор занимает столько времени, сколько занимает более долгий из этих двух.
Пожалуйста, помогите Монокарпу и Поликарпу выбрать задачи и разделить их между собой так, чтобы разбор закончился как можно раньше. Выведите длительность разбора.
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее время, которое может занять разбор, если Монокарп и Поликарп могут выбирать, какие \(k\) из \(n\) задач разбирать и как разделять их между собой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1
|
2
6
5
21
18
1
|