Задача Trainers. Вчителька Галина Петрівна та її колишній учень, а нині студент Вася готують N школярів для участі в олімпіаді з інформатики. Вони підготували по одній задачі і планують пояснити їх кожному школяру. З педагогічних міркувань вони не можуть працювати вдвох з одним школярем одночасно, і жоден із них одночасно не може працювати з кількома школярами. Кожен школяр потребує певний час, аби зрозуміти та реалізувати задачу. Знайдіть, через який мінімальний час від початку занять усі школярі вмітимуть розв'язувати обидві задачі.
Технічні умови Програма Trainers читає з пристрою стандартного введення число N - кількість школярів, а далі у тому ж рядку через пропуски N цілих чисел, де i-е число - час, необхідний для того аби зрозуміти та реалізувати алгоритм (як перший, так і другий), i-му школяру. Всі вхідні дані належать інтервалу від 1 до 3·105 Програма виводить на пристрій стандартного виведення єдине число - шукану величину.
Приклади
| Введення | Введення | Введення |
| 3 2 2 2 | 3 4 1 2 | 4 1 3 2 1 |
| Виведення | Виведення | Виведення |
| 6 | 8 | 7 |
Комментарі до прикладів:
1. Кожен школяр потребує 2 одиниці часу, аби зрозуміти та реалізувати алгоритм. Один з можливих графіків занять: Галина Петрівна пояснює свою задачу послідовно школярам 1, 2, 3, а Вася – 3, 1, 2.
2: Один з оптимальних графіків: Галина Петрівна працює з школярами 2, 3 та 1 відповідно, але з паузою в 1 одиницю часу між 3 і 1. Вася буде працювати зі школярами 1, 3, 2 без пауз.