В лесу возле Васиного дома есть грибная поляна. Поляна состоит из двух рядов, каждый из которых можно разбить на 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
В первом тестовом примере оптимальный маршрут выглядит следующим образом:
Во втором тестовом примере оптимальный маршрут выглядит следующим образом:
