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

Новий Лабіринт Амбера

Новий Лабіринт Амбера

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

Якось Корвіну – принцу Амбера, по якійсь важливій справі терміново знадобилось попасти у саму далеку тінь, яку він тільки знав. Як всім відомо, самий швидкий спосіб подорожей для принців Амбера – це Лабіринт Амбера. Але у Корвіна були настільки важливі справи, що він не хотів витрачати час на спуск у підземелля (саме там знаходиттся Амберський Лабіринт). Тому він вирішив скористатись Новим Лабіринтом, який намалював Дворкін. Але цей Лабіринт не такий простий, як здається…

Новий Лабіринт має вигляд послідовних комірок, які йдуть одна за одною, пронумерованих від 1 до N. З комірки під номером i можна попасти в комірки під номерами i+2 (якщо i+2N) і i+3 (якщо i+3N). У кожній комірці лежить якась кількість золотих монет k_i. Для того, щоб пройти лабіринт, потрібно, починаючи ходити із-за меж лабіринту (з нульової комірки) просуватись за вище описаними правилами, при цьому підбираючи всі монетки у комірках, у яких ви робите проміжні зупинки. Кінцевна мета подорожі – попасти у комірку з номером N. Подальша подорож (у довільне місце Всесвіту) можливо лише тоді, коли достигнувши комірки з номером N, ви зберете максимальну кількість монеток. Напишіть програму, яка допоможе Корвіну взнати, яку максимальну кількість монеток можна зібрати, проходячи Новий Лабіринт Амбера.

Вхідні дані

У першому рядку вхідного файлу міститься натуральне число N (2N100000),а у другому N цілих чисел, відокремлених одним пропуском, k_i – кількість монеток, що лежать у комірці з номером i (0k_i1000).

Вихідні дані

У вихідний файл вивести одне ціле число – максимальну кількість монеток, які можна зібрати, проходячи лабіринт.

Приклад

Вхідні дані #1
5
1000 2 3 1 3
Вихідні дані #1
6