#2343. 乘积

乘积

题目描述

给定两个长为n\red{n}的序列a\red{a}b\red{b}。你可以对a\red{a}的一段区间翻转,也可以不翻转,要求翻转后a\red{a}b\red{b}对应位 置之积的和最大。即求下式的值最大:i=1nai×bi\red{\sum_{i=1}^{n}{a_i\times b_i}}

输入格式

第一行一个整数n\red{n,}表示序列长度。

接下来一行n\red{n}个整数,表示序列a\red{a}

接下来一行n\red{n}个整数,表示序列b\red{b}

输出格式

输出一行一个整数,表示答案。

样例

输入样例1

5
2 3 2 1 3
1 3 2 4 2

输出样例1

29

输入样例2

6
1 8 7 6 3 6
5 9 6 8 8 6

输出样例2

235

提示

对于50%\red{50\%}的数据,1<=n<=50\red{1<=n<=50}

对于100%\red{100\%}的数据,1<=n<=5000,1<=ai,bi<=107\red{1<=n<=5000,1<=a_i,b_i<=10^7}