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.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef   long double ld;
#define syncboost ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define mp make_pair
#define pb push_back
#define pl pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vpl vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define precise(n) cout << fixed; cout << setprecision(n)
#define setbit(x) __builtin_popcount(x)
#define mem(x,val) memset(x,val,sizeof(x))
#define rep(i,init,n) for(ll i = init;i<n;i++)
#define rrep(i,n,init) for(ll i = n;i>=init;i--)
#define fi first
#define sz(x) x.size()
#define se second
long double pi = 3.14159265;
#define show(x) cerr << x
#define deb1(x) cout<<x<<"\n";
#define deb(x) show(#x << ": " << (x) << endl);
#define debn(x) show((x) <<" ");
#define debv(x) for(auto it : x ) debn(it);deb("\n");
#define det(x) cout<<x<<"\n";
#define No cout<<"No\n";
#define Yes cout<<"Yes\n";
#define YES cout<<"YES\n";
#define NO cout<<"NO\n";
#define nl cout<<"\n";
const ll  mod  = 1000000007; 
//const ll  mod  =998244353;
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll power(ll a, ll b, ll m)
{
  if(a == 0) return 0;
  if(b == 0) return 1;
  if(b == 1) return a % m;
  ll temp = power( a , b / 2 , m );
  temp = ( temp * temp ) % m;
  if(b % 2)
    temp = (a * temp) % m;
  return temp;
} 
 ll modinv(ll x) {
    return power(x,mod-2,mod);
}
 
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};

const ll N = 105;  
void prep()
{  
     
	return;
 
}
void solve()
{     //calc pres suf then dp[i][j]l
	
    ll n,i;
    cin>>n;
    ll A[n],B[n];
    for(i=0;i<n;i++)
    {
        cin>>A[i];
    }
    for(i=0;i<n;i++)
    {
        cin>>B[i];
    }
    ll dp[n+1][n+1];
    for(i=1;i<=n;i++)
    {
        dp[i][i]=A[i-1]*B[i-1];
    }
    ll j;
    for(j=1;j<=n;j++)
    {
        for(i=j-1;i>=1;i--)
        {
            if(i==j-1)
                dp[i][j]=A[i-1]*B[j-1]+A[j-1]*B[i-1];
            else
                dp[i][j]=dp[i+1][j-1]+A[i-1]*B[j-1]+A[j-1]*B[i-1];
        }
    }
    ll pref[n+1];
    pref[0]=0;
    for(i=1;i<=n;i++)
    {
        pref[i]=pref[i-1]+A[i-1]*B[i-1];
    }
    ll ans[n+1][2];
    ans[0][0]=0;
    ans[0][1]=0;
    ans[1][1]=A[0]*B[0];
    ans[1][0]=A[0]*B[0];
 
    for(i=2;i<=n;i++)
    {
        ll pr=0;
        ans[i][0]=0;
        ans[i][1]=0;
        for(j=i;j>=1;j--)
        {
            pr+=A[j-1]*B[j-1];
            ans[i][1]=max(ans[i][1],pref[j-1]+dp[j][i]);
            ans[i][0]=max(ans[i][0],max(pref[j-1],ans[j-1][1])+pr);
 
        }
    }
    cout<<max(ans[n][1],ans[n][0]);
	return;
	}
 
signed  main()
{
      ll test = 1;   
      syncboost;
      // cin>> test;
      prep();
      
     
   rep(testcase,1,test+1)
    {   
      //  deb(testcase)
       // cout<<"Case #"<<testcase<<": ";
    	solve( );
    }
 //cerr<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
   return 0;
} 