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.
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

struct fsum { ll l = 0, r = 0; };
int main() {
	int n;cin >> n;
	ll* a = new ll[n];ll* b = new ll[n];ll* sum = new ll[n];fsum* f = new fsum [n*(n+1)/2];ll* sumb = new ll[n]();ll* suma = new ll[n]();
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (i == 0)suma[i] = a[i];
		else  suma[i] = a[i] + suma[i - 1];
	}
	for (int i = 0;i < n;i++) {
		cin >> b[i];
		if (i == 0)sum[i] = a[i] * b[i], sumb[i] = b[i];
		else sum[i] = sum[i - 1] + a[i] * b[i], sumb[i] = b[i] + sumb[i - 1];
		f[((2 * n - i + 1) * i) / 2].r = f[((2 * n - i + 1) * i) / 2].l = a[i] * b[i];
	}
	ll max = sum[n-1];
	for (int l = 1;l < n;l++) {
		for (int r = 0;r+l < n;r++) {
			ll s0 = (suma[l + r] - suma[r]+a[r]) * (sumb[l + r] - sumb[r]+b[r]);
			f[((2 * n - r + 1) * r) / 2 + l].l = s0 - f[((2 * n - r) * (r + 1)) / 2 + l - 1].r;
			f[((2 * n - r + 1) * r) / 2 + l].r = s0 - f[((2 * n - r + 1) * r) / 2 + l - 1].l;
			ll s1 = f[((2 * n - r + 1) * r) / 2 + l].r - f[((2 * n - r) * (r + 1)) / 2 + l - 1].r;
			if (r > 0)s1 += sum[r - 1];
			if (r + l < n - 1)s1 += sum[n - 1] - sum[r + l];
			if (s1 > max)max = s1;
		}
	}
	/*for (int i = 0;i < n;i++) {
		for (int j = 0;j+i < n;j++)cout << f[((2 * n - i + 1) * i) / 2 + j].l << "," << f[((2 * n - i + 1) * i) / 2 + j].r << " ";
		cout << endl;
	}*/
	cout << max << endl;
	return 0;
}