Задача E. Черепашка и гексагон ≡

Условие

Черепашка находится в левом верхнем углу гексагонального поля в форме шестиугольника. Её цель  — переместиться в правый нижний угол, собирая по пути как можно больше монеток, лежащих на каждом шестиугольнике. За один ход черепашка может сместиться в соседний (по стороне) шестиугольник, но только в одном из трех возможных направлений: направо, вниз-вправо и вниз-влево. Какое максимальное количество монеток сможет собрать черепашка?

Формат входных данных

В первой строке входного файла записано натуральное число: n  — размер поля. В следующих 2 ⋅ n − 1 строках приведено описание поля в виде записанных через пробел последовательности чисел m_i, соответствующих количеству монеток, лежащих на соответствующем шестиугольнике. Гарантируется, что все числа  — натуральные.

Формат выходных данных

Выведите одно натуральное число  — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 100

1 ≤ m_i ≤ 100

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n = 2, баллы: 40.

Подзадача 2: 3 ≤ n ≤ 100, баллы: 60.

Пояснение к примерам

Возможные пути черепашки приведены на рисунке выше. Во втором примере есть несколько путей, приносящих черепашке максимальное количество монет.

Примеры тестов

2
1 3
4 3 1
2 1

11

3
2 1 3
4 1 3 1
2 1 3 1 2
5 1 1 3
2 1 2

21