You are given two integer arrays a and b of length n.

You can reverse at most one subarray (continuous subsegment) of the array a. 

Your task is to reverse such a subarray that the sum ∑_{i=1}^n a_i ⋅ b_i is maximized.

Input

The first line contains one integer n (1 ≤ n ≤ 5000).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^7).

The third line contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ 10^7).

Output

Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of a.

Examples

Input


5
2 3 2 1 3
1 3 2 4 2


Output


29


Input


2
13 37
2 4


Output


174


Input


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


Output


235

Note

In the first example, you can reverse the subarray [4, 5]. Then a = [2, 3, 2, 3, 1] and 2 ⋅ 1 + 3 ⋅ 3 + 2 ⋅ 2 + 3 ⋅ 4 + 1 ⋅ 2 = 29.

In the second example, you don't need to use the reverse operation. 13 ⋅ 2 + 37 ⋅ 4 = 174.

In the third example, you can reverse the subarray [3, 5]. Then a = [1, 8, 3, 6, 7, 6] and 1 ⋅ 5 + 8 ⋅ 9 + 3 ⋅ 6 + 6 ⋅ 8 + 7 ⋅ 8 + 6 ⋅ 6 = 235.
//Created by:Coding_lover(05-05-2021 18:40:29)

#ifndef ONLINE_JUDGE
#  define dbg(x) cerr<<"Debugging "<<#x<<":"<<endl;cerr<<#x<<" = "<<x<<endl
#  define dbgv(v) cerr<<"Debugging "<<#v<<":"<<endl; for(ll i=0;i<v.size();i++){cerr<<v[i]<<" ";}cerr<<endl
#else
#  define dbg(x) 0
#  define dbgv(x) 0
#endif

#include <bits/stdc++.h>
#define ll long long
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define INF LLONG_MAX
#define MOD 1000000007
#define f first
#define s second
#define LB lower_bound
#define UB upper_bound
#define gcd(a,b)  __gcd((a),(b))
#define lcm(a,b)  ((a)*(b)) / gcd((a),(b))
#define pi pair<long long,long long>
#define pii pair<long long,pi>
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define vc vector
#define vll vector<long long>
#define rep(i, a, n) for (ll i = a; i < (long long)n; ++i)
#define repe(i, a, n) for (ll i = a; i <= (long long)n; ++i)
#define repr(i, n, a) for (ll i = n; i > (long long)a; --i)
#define repre(i, n, a) for (ll i = n; i >= (long long)a; --i)
using namespace std;
int main() {
  FASTER;
  ll test=1;
  //cin >> test;
  while (test--) {
	ll n;
	cin>>n;
	vll a(n),b(n);
	for(auto &i:a)cin>>i;
	for(auto &i:b)cin>>i;
	ll dp[n][n];
	ll pref[n];
	pref[0]=a[0]*b[0];
	for(ll i=1;i<n;i++){
		pref[i]=pref[i-1]+a[i]*b[i];
	}
	ll sum=pref[n-1];
	ll ans=sum;
	for(int i=0;i<n;i++)dp[0][i]=a[i]*b[i];
  	for(int len=1;len<n;len++){
  		for(int i=0;i+len<n;i++){
  			if(len==0)dp[len][i]=a[i]*b[i];
  			else if(len==1)dp[len][i]=a[i]*b[i+1]+a[i+1]*b[i];
  			else{
  				dp[len][i]=dp[len-2][i+1]+a[i]*b[i+len]+a[i+len]*b[i];
  			}
  			ll rest=0;
  			//cout<<i<<" "<<len<<endl;
  			if(i!=0)rest=pref[i-1];
  			if(i+len-1<n-1 and i+len>=0)rest+=(sum-pref[i+len]);
  			//dbg(rest);
  			//dbg(rest+dp[len][i]);
  			ans=max(ans,rest+dp[len][i]);
  		}
  	}
  	cout<<ans<<endl;
  }
  return 0;
}