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.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.security.KeyPair;
import java.util.*;
import  java.lang.*;
public class A710 {

    static BufferedReader br;
    static long mod = 1000000000 + 7;
    static HashSet<Integer> p ;

    static int spf[] ;
    static long ans=1;
    static HashSet<Integer>[] graph;
    static boolean[] vis;
    static int[] col;
    static int[] lvl;
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
        // tc=cinI();
        int n =cinI();
        long[] a =readArray(n,0);
        long[] b= readArray(n,0);
        long[][] dp =new long[n][n];
        long[]prefi = new long[n];
        long ans=0;
        long[] suff= new long[n];
        for(int i=0;i<n;i++){
            ans = ans + (a[i]*b[i]);
            prefi[i]=ans;
        }
        long x=0;
        for(int i=n-1;i>=0;i--){
            x+=(a[i]*b[i]);
            suff[i]=x;
        }

//    for(int i=0;i<n;i++){
//        System.out.print(prefi[i]+" ");
//    }
//        System.out.println();
//
//        for(int i=0;i<n;i++){
//            System.out.print(suff[i]+" ");
//        }
        for(int i=0;i<n;i++){



            dp[i][i]=a[i]*b[i];
        }
        for(int i=0;i<n-1;i++){




            dp[i][i+1]= (b[i+1]*a[i])+ (a[i+1]*b[i]);

        }

        for(int length=3;length<=n;length++){
            for(int j=0;j<n;j++){
                int r = j+length-1;
                if(r>=n){
                    break;
                }
                long y=0;

                dp[j][r]=(a[r]*b[j])+dp[j+1][r-1]+(b[r]*a[j]);
            }
        }
        //  System.out.println(ans);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(j<=i){
                    continue;
                }

                long r =0;
                if(i-1>=0){
                    r+=prefi[i-1];
                   // y=prefi[i-1];
                }

                if(j+1<n){
                    r+=suff[j+1];
                  //  z=suff[j+1];
                }

                ans=max(ans,dp[i][j]+r);
                // System.out.print(dp[i][j]+" "+y+" "+z+" || ");
            }
            // System.out.println();
        }
        System.out.println(ans);


    }

    private static long recursion(int i,int par) {

        //  System.out.println("Entr "+i+" par "+par+" col "+col[i]);
        long ret=1;
        vis[i]=true;

        for(int c:graph[i]){

            if(vis[c] ==true){
                //   System.out.println("Visited "+c+" Current "+i+" parn "+par );
                if(col[c]==col[i]){
                    return 0l;
                }
                continue;
            }
            lvl[c]=lvl[i]+1;
            long tem=0;
            for(int j=1;j<=3;j++){
                if(col[i]==j){
                    continue;

                }
                col[c]=j;
                // vis[c]=true;
                tem+=recursion(c,i);
                col[c]=0;

            }
            ret*=tem;
        }
        // System.out.println("Exit "+i+ " pare "+par+" col "+col[i]);
        return ret;
    }


    // Calculating SPF (Smallest Prime Factor) for every
    // number till MAXN.
    // Time Complexity : O(nloglogn)
    static void sieve(int MAXN)
    {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)

            // marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;

        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)

                    // marking spf[j] if it is not
                    // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }

    // A O(log n) function returning primefactorization
    // by dividing by smallest prime factor at every step
    static boolean getFactorization(int x,HashSet<Integer> r) {
        boolean ans=true;
        while (x != 1) {
            //ret.add(spf[x]);
            if(r.contains(spf[x])==false){
                r.add(spf[x]);

            }
            else{
                ans=false;
                break;
            }
            x = x / spf[x];
        }
        return ans;
    }


    private static int dfs(TreeMap<Integer, HashSet<Integer>> graph, boolean[] vis, Integer key, Stack<Integer> st) {
        if (st.size() == 0) {
            return 0;
        }
        int par = st.pop();

        HashSet<Integer> child = graph.get(par);
        vis[par] = true;
        int nodes = 1;
        for (int c : child) {
            if (vis[c] == false) {
                st.add(c);
                nodes += dfs(graph, vis, c, st);
            }
        }
        return nodes;
    }


    public static boolean isSorted(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }


    private static int gcd(int a, int b) {
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a % b, b);
        return gcd(a, b % a);
    }


    public static long min(long a, long b) {
        return Math.min(a, b);
    }

    public static int min(int a, int b) {
        return Math.min(a, b);
    }


    public static void sieve() {
        int[] pf = new int[100000000 + 1];
        //0 prime //1 not prime
        pf[0] = 1;
        pf[1] = 1;
        for (int j = 2; j <= 10000; j++) {

            if (pf[j] == 0) {
                p.add(j);
                for (int k = j * j; k < pf.length; k += j) {
                    pf[k] = 1;
                }
            }
        }

    }


    public static int[] readArray(int n, int x, int z) throws Exception {
        int[] arr = new int[n];
        String[] ar = cinA();
        for (int i = x; i < n + x; i++) {
            arr[i] = getI(ar[i - x]);
        }
        return arr;
    }

    public static long[] readArray(int n, int x) throws Exception {
        long[] arr = new long[n];
        String[] ar = cinA();
        for (int i = x; i < n + x; i++) {
            arr[i] = getL(ar[i - x]);
        }
        return arr;
    }

    public static void arrinit(String[] a, long[] b) throws Exception {
        for (int i = 0; i < a.length; i++) {
            b[i] = Long.parseLong(a[i]);
        }
    }

    public static HashSet<Integer>[] Graph(int n, int edge, int directed) throws Exception {
        HashSet<Integer>[] tree = new HashSet[n];

        for (int j = 0; j < edge; j++) {

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if (directed == 0) {

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }

    public static void arrinit(String[] a, int[] b) throws Exception {
        for (int i = 0; i < a.length; i++) {
            b[i] = Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }

    public static String[] cinA(int x) throws Exception {
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }

    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}
