В лесу возле Васиного дома есть грибная поляна. Поляна состоит из двух рядов, каждый из которых можно разбить на n последовательных клеток. Про каждую клетку Вася знает число — на сколько грамм тяжелеют грибы в этой клетке за минуту. Перемещение в соседнюю клетку занимает у Васи ровно одну минуту, выходить за пределы поляны Вася не может. Две клетки считаются соседними, если у них есть общая сторона. Когда Вася приходит в клетку, он собирает все растущие там грибы.
Вася начинает свое путешествие в левой верхней клетке. Каждую минуту Вася должен переходить в соседнюю клетку, он не может ждать, пока грибы вырастут. Он хочет посетить все клетки ровно по одному разу и максимизировать при этом суммарный вес собранных грибов. Изначально все грибы имеют вес 0. Обратите внимание, что Васе не обязательно возвращаться в стартовую клетку.
Помогите Васе! Сообщите ему максимальный суммарный вес грибов, который он может собрать.
Выходные данные
Выведите одно число — максимальный суммарный вес грибов, которые может получить Вася, выбрав оптимальный маршрут. Обратите внимание, что каждую клетку поляны Вася обязан посетить ровно один раз.
Примечание
В первом тестовом примере оптимальный маршрут выглядит следующим образом:
Таким образом, собраный вес грибов будет
0·1 + 1·2 + 2·3 + 3·4 + 4·5 + 5·6 = 70.
Во втором тестовом примере оптимальный маршрут выглядит следующим образом:
Таким образом, собраный вес грибов будет
0·1 + 1·10 + 2·100 + 3·1000 + 4·10000 + 5·100000 = 543210.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
6 5 4
|
70
|
|
2
|
3
1 1000 10000
10 100 100000
|
543210
|