题目描述

约翰的${2N(3<=N<=1000)}$只奶牛正打算举办一场音乐会来吸收资金，其中，${N}$只奶牛是手风琴手，而另${N}$只奶牛是班卓琴手，每个手风琴手有一个天才指数${A_i(0<=A_i<=1000)，}$同样每一个班卓琴手有一个天才指数${B_i(0<=A_i<=1000).}$

约翰打算给手风琴手和班卓琴手配对，如果让手风琴手${i}$与班卓琴手;配对，她们吸收的资金将是${A_i\times B_j}$所以约翰可以用他的聪明才智选择一种最好的搭配方式，让奶牛们吸收的总资金最大化.

不幸的是，约翰的手风琴手有一个怪癖;如果手风琴手${i}$已经和班卓琴手${j}$配对，那手风琴手${i+1}$到${N，}$绝不肯与班卓琴手${1}$到${j-1}$间的某一个配对，这让给约翰的搭配计划造成了很多不便，而且，约翰也意识到，适当地让一些奶牛放弃配对，不要参加音乐会，会让吸收的总资金更大.

然而，那些失去演出机会的失落奶牛，为了消解她们的孤独与痛苦，正成群结队地到洒吧去喝冰镇橙味酒.如果从${x}$号到${y}$号手风琴手均是失落的奶牛(${x-1}$号和${y+1}$号奶牛不存在或参加了演出)，$这${y-x+1}$只奶牛会结成一伙去喝酒，而且她们的消费量是

${(\sum_{k=x}^{y}{A_k})^2}$

同样，对于班卓琴手也有这样的规律 面对未来可能产生的巨额酒费支出，约翰不得不再认真考虑他的配对计划了，请你帮忙计算最大的收益会是多少？

输入格式

第${1}$行输入${N，}$之后${N}$行输入${A_i，}$之后${N}$行输入${B_i}$．

输出格式

输出最大收益

样例

输入样例

3
1
1
5
5
1
1

输出样例

17

提示

手风琴手${3}$和班卓琴手${1}$搭配，创造收益${25}$美元．手风琴手${1}$和手风琴手${2}$喝酒用了${4}$美元．同样班卓琴手${2}$和班卓琴手${3}$用了${4}$美元．最后收益为${25 -4-4=17}$美元．