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.
using namespace std;
#include <bits/stdc++.h>
#define ll long long
long long dp[5000 + 1][5000 + 1];
struct item
{
    long long a;
};
struct segtree
{
    int size;
    int ele;
    item single(long long v)
    {
        return {v};
    }
    item NEUTRAL_ELEMENT = {0ll};
    vector<item> values;
    void init(int n)
    {
        ele = n;
        size = 4 * n + 1;
        values.resize(size);
    }
    item merge(item x, item y)
    {
        return {x.a + y.a};
    }
    void build(int *arr, int *arr1)
    {
        build(arr, arr1, 1, 0, ele - 1);
    }
    void build(int *arr, int *arr1, int index, int s, int e)
    {
        if (s > e)
            return;
        if (s == e)
        {
            //cerr << 1 << endl;
            long long val = (ll)arr[s+1] * (ll)arr1[s+1];
            values[index] = single(val);
            return;
        }
        int mid = (s + e) / 2;
        build(arr, arr1, 2 * index, s, mid);
        build(arr, arr1, 2 * index + 1, mid + 1, e);
        values[index] = merge(values[2 * index], values[2 * index + 1]);
    }
    void update(int i, int val)
    {
        update(0, ele - 1, 1, val, i);
    }
    void update(int s, int e, int index, int val, int i)
    {
        if (i < s || i > e)
            return;
        else if (s == e)
        {
            values[index] = single(val);
            return;
        }
        int mid = (s + e) / 2;
        update(s, mid, 2 * index, val, i);
        update(mid + 1, e, 2 * index + 1, val, i);
        values[index] = merge(values[2 * index], values[2 * index + 1]);
    }
    item query(int qs, int qe)
    {
        return query(0, ele - 1, qs, qe, 1);
    }
    item query(int s, int e, int qs, int qe, int index)
    {
        if (qs > e || qe < s)
            return NEUTRAL_ELEMENT;
        if (s >= qs && e <= qe)
            return values[index];
        int mid = (s + e) / 2;
        item lans = query(s, mid, qs, qe, 2 * index);
        item rans = query(mid + 1, e, qs, qe, 2 * index + 1);
        return merge(lans, rans);
    }
};
void solve()
{
    int n, m;
    cin >> n;
    int arr[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    int arr1[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> arr1[i];
    arr[0] = 1;
    arr1[0] = 1;
    memset(dp, 1, sizeof(dp));
    for (int i = 1; i <= n; i++)
        dp[i][i] = (ll)arr[i] * (ll)arr1[i];
    for (int i = 1; i < n; i++)
    {
        dp[i][i + 1] = ((ll)arr[i] * (ll)arr1[i + 1] + ((ll)arr[i + 1] * (ll)arr1[i]));
    }
    for (int k = 3; k <= n; k++)
    {
        for (int i = 1; i + k - 1 <= n; i++)
        {
            int j = i + k - 1;
            long long val1 = dp[i + 1][j - 1];
            long long val2 = (ll)arr[i] * (ll)arr1[j] + (ll)arr[j] * (ll)arr1[i];
            dp[i][j] = val1 + val2;
        }
    }
    segtree tree;
    tree.init(n);
    tree.build(arr, arr1);
    auto getst = [&](int i, int j) {
        if (i <= 0 || j <= 0)
            return 0ll;
        if (i > n || j > n)
            return 0ll;
        return tree.query(i-1,j-1).a;
    };
    auto rev = [&](int i, int j) {
        if (i > n || j > n)
            return 0ll;
        if (i <= 0 || j <= 0)
            return 0ll;
        return dp[i][j];
    };
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            // reverse the portion in the range i to j
            ll val1 = getst(1, i - 1);
            ll val2 = getst(j + 1, n);
            ll val3 = rev(i, j);
            ll val = val1 + val2 + val3;
            ans = max(ans, val);
        }
    }
    cout << ans << endl;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}
