C. Вася и грибы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В лесу возле Васиного дома есть грибная поляна. Поляна состоит из двух рядов, каждый из которых можно разбить на n последовательных клеток. Про каждую клетку Вася знает число — на сколько грамм тяжелеют грибы в этой клетке за минуту. Перемещение в соседнюю клетку занимает у Васи ровно одну минуту, выходить за пределы поляны Вася не может. Две клетки считаются соседними, если у них есть общая сторона. Когда Вася приходит в клетку, он собирает все растущие там грибы.

Вася начинает свое путешествие в левой верхней клетке. Каждую минуту Вася должен переходить в соседнюю клетку, он не может ждать, пока грибы вырастут. Он хочет посетить все клетки ровно по одному разу и максимизировать при этом суммарный вес собранных грибов. Изначально все грибы имеют вес 0. Обратите внимание, что Васе не обязательно возвращаться в стартовую клетку.

Помогите Васе! Сообщите ему максимальный суммарный вес грибов, который он может собрать.

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

Первая строка содержит число n (1 ≤ n ≤ 3·105) — длина поляны.

Вторая строка содержит n чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — скорость роста грибов в первом ряду поляны.

Третья строка содержит n чисел b1, b2, ..., bn (1 ≤ bi ≤ 106) — скорость роста грибов во втором ряду поляны.

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

Выведите одно число — максимальный суммарный вес грибов, которые может получить Вася, выбрав оптимальный маршрут. Обратите внимание, что каждую клетку поляны Вася обязан посетить ровно один раз.

Примеры
Входные данные
3
1 2 3
6 5 4
Выходные данные
70
Входные данные
3
1 1000 10000
10 100 100000
Выходные данные
543210
Примечание

В первом тестовом примере оптимальный маршрут выглядит следующим образом:

Таким образом, собраный вес грибов будет 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.