Code Submission Evaluation System Login

KILO 2018 5/5

Start:2018-10-04 16:30:00
End:2018-10-04 18:30:00
 

Tasks | Scoreboard | Statistics


CSES - KILO 2018 5/5 - AlgorithmCSES - Algorithm

Algorithm

Time limit:1.00 s
Memory limit:128 MB

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
Example

Input:
3
3 1 4
2 7 2


Output:
21