Uolevi found a description of an algorithm in an old book. It was stated that the algorithm does something really astonishing, but there was no further explanations what the algorithm does. Unfortunately, the implementation of the algorithm was so slow that Uolevi couldn't use it for large inputs.

The code of the algorithm is as follows:

long f(int i, int j, long a[], long b[], int n) {
    if (i >= n) return 0;
    swap(a[i],a[j]);
    long r = a[i]*b[i] + f(i+1,i+1,b,a,n);
    swap(a[i],a[j]);
    if (j < n-2) {
        r = min(r, f(i,j+2,a,b,n));
    }
    return r;
}

The algorithm is called f(0,0,a,b,n) where a and b are two arrays of long numbers. Both arrays are zero-indexed and contain n numbers.

Could you help Uolevi to implement the algorithm more efficiently?

Input

The first line of input contains a single integer, n. The second line contains the numbers in array a. The third line contains the numbers in array b.

Output

Output the value of f(0,0,a,b,n).

Constraints

• n is between 1 \ldots 10^5
• each array number is between 1 \ldots 10^5

Example

Input:

3
3 1 4
2 7 2

Output:

21