题目描述

佩奇住在森林里，附近有一个会长蘑菇的空地。

这个空地被分成两行，每行分为 $\red{n}$个连续的格子。佩奇知道每分钟每个格子里能长多少个蘑菇。

他要花一分钟从一个格子走到相邻的格子上，并且他不能离开空地。（我们称两个格子相邻，当且仅当它们有公共边。）当 佩奇进入一个格子时，他会马上收集那个格子里的所有蘑菇。

佩奇从左上角的格子开始收集蘑菇。因为他等不及蘑菇生长了，所以每分钟内他必须移动到一个相邻格子。

他想每个格子都恰好走一遍并且最大化他所收集的蘑菇数量。一开始所 有格子都没有蘑菇。佩奇也不一定要回到开始的格子。

帮帮 佩奇！计算出他能收集到的最大蘑菇数量。

输入格式

第一行一个整数 $\red{n}$

第二行$\red{n }$个整数 $\red{a_i，}$表示第一行蘑菇的生长速度

第三行 $\red{n}$个整数 $\red{b_i，}$表示第二行蘑菇的生长速度

输出格式

一个整数，能够采到的最大蘑菇数量。

样例

输入样例1

3

1 2 3 

6 5 4

输出样例1

70

输入样例2

3

1 1000 10000 

10 100 100000

输出样例2

543210

提示

样例$\red{1:(1,1)→}$$\red{(1,2) →}$ $\red{(1,3) →}$ $\red{(2,3) →}$ $\red{(2,2) →}$ $\red{(2,1)}$

获得的分数为$\red{0×}$$\red{1+1×}$$\red{2+2×}$$\red{3+3×}$$\red{4+4×}$$\red{5+5×}$$\red{6=70}$

对于$\red{30\%}$的数据满足, $\red{1<=n<=10^3}$

对于$\red{100\%}$的数据满足, $\red{1<=n<=3×}$$\red{10^5,1<=a_i,b_i<=10^6}$