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 sys;input=sys.stdin.readline
# from itertools import accumulate
# from decimal import *
# import math
# getcontext().prec = 50
# input().strip()
# int(input())
# list(map(int,input().split()))
# map(int,input().split())
# def solve():
# chars = 'abcdefghijklmnopqrstuvwxyz'


# for _ in range(int(input())):
#     solve()    
# print()
def solve():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    init = 0
    for i in range(n):
        init+=a[i]*b[i]
    dp1 = [0 for j in range(n)]
    dp2 = [0 for j in range(n)]
    m = 0
    for i in range(1,n):
        a1,a2 = a[i],a[i-1]
        b1,b2 = b[i],b[i-1]
        val = 0-a1*b1-a2*b2+a1*b2+b1*a2
        dp2[i] = val
        m = max(m,val)
    ch = 0
    for i in range(2,n):
        for j in range(i-1):
            if (i+j)%2==0:
                
                a1,a2 = a[j],a[i]
                b1,b2 = b[j],b[i]
                dp1[(i+j+1)//2] = dp1[(i+j+1)//2]+(a1-a2)*(b2-b1)
                m = max(m,dp1[(i+j+1)//2])
            else:
                a1,a2 = a[j],a[i]
                b1,b2 = b[j],b[i]
                dp2[(i+j+1)//2] = dp2[(i+j+1)//2]+(a1-a2)*(b2-b1)
                m = max(m,dp2[(i+j+1)//2])
    print(str(m+init))
        
            
            
    
        
    
solve()
# for _ in range(int(input())):
#     solve()    