You are given a rectangular table 3 × n. Each cell contains an integer. You can move from one cell to another if they share a side.

Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of columns in the table.

Next three lines contain n integers each — the description of the table. The j-th number in the i-th line corresponds to the cell aij ( - 109 ≤ aij ≤ 109) of the table.

Output

Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn't visit any of the cells twice.

Examples

Input

3
1 1 1
1 -1 1
1 1 1


Output

7


Input

5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10


Output

110

Note

The path for the first example:

<image>

The path for the second example:

<image>
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/*
 public class _762D {

 }

 */

public class _762D
{
	long minf = (long) -1e16;

	public void solve() throws FileNotFoundException
	{
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		// actual solution

		int n = inputHelper.readInteger();

		long[][] a = new long[n][3];

		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < n; j++)
			{
				a[j][i] = inputHelper.readInteger();
			}
		}

		long[][][][][] dp = new long[n][2][2][2][3];

		for (int i = 0; i < n; i++)
		{
			for (int j1 = 0; j1 < 2; j1++)
			{
				for (int j2 = 0; j2 < 2; j2++)
				{
					for (int j3 = 0; j3 < 2; j3++)
					{
						for (int k = 0; k < 3; k++)
						{
							dp[i][j1][j2][j3][k] = minf;
						}
					}
				}
			}
		}

		dp[0][1][0][0][0] = a[0][0];
		dp[0][1][1][0][1] = a[0][0] + a[0][1];
		dp[0][1][1][1][2] = a[0][0] + a[0][1] + a[0][2];

		for (int i = 1; i < n; i++)
		{
			for (int j1 = 0; j1 < 2; j1++)
			{
				for (int j2 = 0; j2 < 2; j2++)
				{
					for (int j3 = 0; j3 < 2; j3++)
					{
						for (int k = 0; k < 3; k++)
						{
							if (j1 + j2 + j3 == 2 && j2 == 0)
								continue;

							if (j1 + j2 + j3 == 3 && k == 1)
								continue;

							if (j1 == 0 && k == 0)
								continue;

							if (j2 == 0 && k == 1)
								continue;

							if (j3 == 0 && k == 2)
								continue;

							dp[i][j1][j2][j3][k] = cal(dp, a, i, j1, j2, j3, k);
						}
					}
				}
			}
		}

		long ans = minf;
		for (int j1 = 0; j1 < 2; j1++)
		{
			for (int j2 = 0; j2 < 2; j2++)
			{
				if (j1 == 1 && j2 == 0)
					continue;
				ans = Math.max(ans, dp[n - 1][j1][j2][1][2]);
			}
		}

		System.out.println(ans);
		// end here
	}

	long cal(long[][][][][] dp, long[][] a, int i, int j1, int j2, int j3, int k)
	{
		long ans = minf;
		if (j1 + j2 + j3 == 1)
		{
			ans = calcUtil(dp, a, i, j1, j2, j3, k);
		}
		else if (j1 + j2 + j3 == 2)
		{
			int ck;
			if (j1 == j2)
			{
				ck = 1 - k;
				ans = calcUtil(dp, a, i, j1, j2, j3, ck);
				if (k == 0)
					ans += a[i][0];
				else if (k == 1)
					ans += a[i][1];
			}
			if (j2 == j3)
			{
				if (k == 1)
					ck = 2;
				else
					ck = 1;
				ans = calcUtil(dp, a, i, j1, j2, j3, ck);
				if (k == 1)
					ans += a[i][1];
				else if (k == 2)
					ans += a[i][2];
			}
		}
		else if (j1 + j2 + j3 == 3)
		{
			if (k == 0)
			{
				ans = calcUtil(dp, a, i, j1, j2, j3, 2);
				ans += a[i][1] + a[i][0];
				ans = Math.max(ans, dp[i - 1][0][0][1][2] + a[i - 1][0]
						+ a[i - 1][1] + a[i][0] + a[i][1] + a[i][2]);
			}

			if (k == 2)
			{
				ans = calcUtil(dp, a, i, j1, j2, j3, 0);
				ans += a[i][1] + a[i][2];
				ans = Math.max(ans, dp[i - 1][1][0][0][0] + a[i - 1][1]
						+ a[i - 1][2] + a[i][0] + a[i][1] + a[i][2]);
			}
		}

		return ans;
	}

	public long calcUtil(long[][][][][] dp, long[][] a, int i, int j1, int j2,
			int j3, int k)
	{
		long ans = minf;

		long ta1 = minf;
		if (k == 0)
		{
			ta1 = Math.max(a[i][0] + dp[i - 1][1][0][0][0], ta1);
			ta1 = Math.max(a[i][0] + dp[i - 1][1][1][0][0], ta1);
			ta1 = Math.max(a[i][0] + dp[i - 1][1][1][1][0], ta1);

			ans = ta1;
		}

		long ta2 = minf;
		if (k == 1)
		{
			ta2 = Math.max(a[i][1] + dp[i - 1][1][1][0][1], ta2);
			ta2 = Math.max(a[i][1] + dp[i - 1][0][1][0][1], ta2);
			ta2 = Math.max(a[i][1] + dp[i - 1][0][1][1][1], ta2);

			ans = ta2;
		}

		long ta3 = minf;
		if (k == 2)
		{
			ta3 = Math.max(a[i][2] + dp[i - 1][1][1][1][2], ta3);
			ta3 = Math.max(a[i][2] + dp[i - 1][0][1][1][2], ta3);
			ta3 = Math.max(a[i][2] + dp[i - 1][0][0][1][2], ta3);

			ans = ta3;
		}

		return ans;
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		(new _762D()).solve();
	}

	class InputHelper
	{
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream)
		{
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					String line = bufferedReader.readLine();
					if (line == null)
					{
						return null;
					}
					tokenizer = new StringTokenizer(line);
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger()
		{
			return Integer.parseInt(read());
		}

		public Long readLong()
		{
			return Long.parseLong(read());
		}
	}
}