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

Печеньки

Печеньки

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Одного разу Бараш вирішив пригостити Нюшу вівсяним печивом. Нюша з задоволенням погодилась, але запропонувала розділити їх якомога честніше. Так трапилось, що у Бараша було 2n печеньок, і було б логічно розділити їх порівну, але тут виявилось, что печеньки мають різну вагу.

І Нюша запролонувала наступну гру. Гра складається з n ходів, у ході яких гравці беруть по одній печеньці у деякому порядку. На першому ході першою бере печеньку Нюша. Після кожного ходу Бараш і Нюша зважують вже вибрані печеньки і той, у кого наприкінці ходу вони важать менше, бере у наступний раз першим. У випадку рівності ваг наприкінці ходу, порядок залишається попереднім.

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

Вхідні дані

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

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

Вихідні дані

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

Приклад

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