Новый Лабиринт Амбера - Задачи - Новый Лабиринт Амбера - Задачи

prb595 Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

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

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

В первой строке входного файла содержится натуральное число N (2 ≤ N ≤ 100000),а во второй N целых чисел, разделенных одним пробелом, k_i – количество монеток лежащих в ячейке с номером i (0 ≤ k_i ≤ 1000).

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

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

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

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

Sample 1
5
1000 2 3 1 3

Sample 2
2
1 2

Sample 3
4
1 3 100 0

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

Sample 1
6

Sample 2
2

Sample 3
3