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.*;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main
{
	static final boolean INPUT_FROM_FILE = false;
	static final String INPUT_FILE = "input/input.txt";
	static final String OUTPUT_FILE = "input/output.txt";
	static final int INF = (int) 1e9;
	static FastReader in;
	static FastWriter out;
	static long[] a = new long[5001];
	static long[] b = new long[5001];
	static long[][] dp = new long[5001][5001];

	static
	{
		try
		{
			in = new FastReader();
			out = new FastWriter();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

	public static void main(String[] args) throws IOException
	{
		int t = 1;
		while (t-- > 0) solve();
		out.close();
	}

	private static long reverseSum(int x, int y)
	{
		if (x > y) return 0;
		if (dp[x][y] == -1)
		{
			if (x == y) dp[x][y] = a[x] * b[y];
			else
			{
				dp[x][y] = a[x] * b[y] + a[y] * b[x] + reverseSum(x + 1, y - 1);
			}
		}
		return dp[x][y];
	}

	private static void solve()
	{
		int n = in.nextInt();
		for (int i = 0; i < n; i++) a[i] = in.nextInt();
		for (int i = 0; i < n; i++) b[i] = in.nextInt();

		long[] pref = new long[n];
		pref[0] = a[0] * b[0];

		for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);

		for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + (a[i] * b[i]);
		long answer = pref[n - 1];

		for (int i = 0; i < n; i++)
		{
			for (int j = i; j < n; j++)
			{
				long original = pref[j];
				if (i > 0) original -= pref[i - 1];
				long reverse = reverseSum(i, j);
				if (reverse > original)
				{
					answer = Math.max(answer, pref[n - 1] + reverse - original);
				}
			}
		}
		out.println(answer);
	}

	static class FastReader
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private BufferedReader br;

		public FastReader() throws FileNotFoundException
		{
			if (INPUT_FROM_FILE)
			{
				this.stream = new FileInputStream(INPUT_FILE);
				br = new BufferedReader(new FileReader(INPUT_FILE));
			} else
			{
				this.stream = System.in;
				br = new BufferedReader(new InputStreamReader(System.in));
			}
		}

		public int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();

			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}

				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine()
		{
			String str = "";
			try
			{
				str = br.readLine();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}
			return str;
		}

		public int nextInt()
		{
			int c = read();

			while (isSpaceChar(c))
				c = read();

			int sgn = 1;

			if (c == '-')
			{
				sgn = -1;
				c = read();
			}

			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c));

			return res * sgn;
		}

		public long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;

			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public double nextDouble()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.')
			{
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.')
			{
				c = read();
				double m = 1;
				while (!isSpaceChar(c))
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public String readString()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			}
			while (!isSpaceChar(c));

			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next()
		{
			return readString();
		}

		public interface SpaceCharFilter
		{
			boolean isSpaceChar(int ch);
		}
	}

	static class FastWriter
	{
		BufferedWriter writer;
		StringBuilder sb;

		public FastWriter() throws IOException
		{
			if (INPUT_FROM_FILE) writer = new BufferedWriter(new FileWriter(OUTPUT_FILE));
			else writer = new BufferedWriter(new PrintWriter(System.out));
			sb = new StringBuilder();
		}

		public void print(Object obj)
		{
			sb.append(obj);
		}

		public void println(Object obj)
		{
			sb.append(obj).append('\n');
		}

		public void close() throws IOException
		{
			writer.write(sb.toString());
			writer.close();
		}
	}
}

