eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Печеньки

Печеньки

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Как-то раз Бараш решил угостить Нюшу овсяным печеньем. Нюша с удовольствием согласилась, но предложила поделить их как можно честнее. Так получилось, что у Бараша было 2n печенек, и было бы логично разделить их поровну, но тут обнаружилось, что печеньки имеют разный вес.

И Нюша предложила следующую игру. Игра состоит из n ходов, в ходе которых игроки берут по одной печеньке в некотором порядке. На первом ходу первой берёт печеньку Нюша. После каждого хода Бараш и Нюша взвешивают уже выбранные печеньки и тот, у кого на конец хода они весят меньше, берёт в следующий раз первым. В случае равенства весов в конце хода, порядок остается прежним.

Несмотря на то, что в конце каждый игрок получит одинаковое количество печенек, их суммарный вес может различаться. Нюша просит подсчитать вас максимальный суммарный вес печенек, который она может гарантированно набрать своими ходами, независимо от ходов Бараша.

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

Первая строка входного файла содержит единственное число n (1n7) - сколько печенек в конце игры получат и Нюша, и Бараш.

Вторая строка входного файла содержит 2n натуральных чисел a_i (1a_i100) - веса печенек в граммах, записанные в неубывающем порядке.

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

В выходной файл выведите единственное число - максимальный суммарный вес печенек, который может гарантированно получить Нюша.

Пример

Входные данные #1
2
1 2 3 4
Выходные данные #1
5
Автор А.Цыпленков, С.Поромов