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.
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define l(i,a,b) for(lli i=a;i<b;i++)
#define lr(i,a,b) for(lli i=a;i>=b;i--)
#define sl(i,m) for(auto i= s.begin();i!=m.end();++i)
#define ll long long
#define lli long long int
#define ld long double
#define vec vector<int>
#define mii map<long int,long int>
#define vl vector<long long>
#define se set <long long int>
#define pi pair<long long,long long>
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
#define tc lli te;i(te);l(t,1,te+1)
#define all(v) v.begin(), v.end()
#define i(x) cin>>x
#define o(x) cout<<x
#define N 300000
#define mod 1000000007
#define nl cout<<"\n";
#define SYNC ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    SYNC
    lli n;
    i(n);
    vl a(n),b(n);
    l(i,0,n)
    i(a[i]);
    l(i,0,n)
    i(b[i]);
    vl pre(n+1,0);
    l(i,1,n+1)
        pre[i]=pre[i-1]+a[i-1]*b[i-1];
    lli ans=pre[n];
    l(i,0,n)
    {
        lli l=i-1,r=i+1,cur=a[i]*b[i];
        while(l>=0&&r<n)
        {
            cur+=a[l]*b[r];
            cur+=a[r]*b[l];
            ans=max(ans,cur+pre[l]+pre[n]-pre[r+1]);
            l--;r++;
        }
        l=i,r=i+1,cur=0;
        while(l>=0&&r<n)
        {
            cur+=a[l]*b[r];
            cur+=a[r]*b[l];
            ans=max(ans,cur+pre[l]+pre[n]-pre[r+1]);
            l--;r++;
        }
    }
    o(ans);
}
