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.BufferedInputStream;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class DEdu17 implements Runnable{
	static long[] MEMO;
	static long[][] mat;
	static final int[] d = {-3,-1,1,3};
	static int N;
	static final long oo = (long)1e16;
	static ArrayDeque<Integer> q = new ArrayDeque<>();
	static int[][][] adj;
	public static void main(String[] args) {
		new Thread(null, new DEdu17(), "c", 1<<26).start();
	}
	static final Random r = new Random();
	public void run() {
		Jolty scan = new Jolty(System.in);
		
		N = scan.nextInt();
		mat = new long[3][N];
		for(int i=0;i<3;i++){
			for(int j=0;j<N;j++){
				mat[i][j] = scan.nextInt();
			}
		}
		if(N==1){
			long sol = 0;
			for(int i=0;i<3;i++){
				sol+=mat[i][0];
			}
			System.out.println(sol);
			return;
		}
		adj = new int[3][3][];
		for(int i=0;i<3;i++){
			int mask = (1<<i);
			int row = i;
			for(int j=0;j<3;j++){
				ArrayList<Integer> temp = new ArrayList<>();
				q.add(((mask<<3)+row));
				while(!q.isEmpty()){
					int X = q.poll();
					int idx = X&7;
					X>>=3;
					int tmask = X&(63);
					
					if(idx==j+3){
						temp.add(tmask);
						continue;
					}
					for(int k=0;k<4;k++){
						if(k==1&&idx==3)continue;
						if(k==2&&idx==2)continue;
						int idx2 = (int)idx+d[k];
						if(idx2<0||idx2>5)continue;
						if((tmask&(1<<idx2))!=0)continue;
						q.add(((tmask|(1<<idx2))<<3)+idx2);
					}
				}
				adj[i][j] = new int[temp.size()];
				for(int k=0;k<temp.size();k++)adj[i][j][k] = temp.get(k);
			}
		}
		
		
		MEMO = new long[3*(1<<3)*N];
		Arrays.fill(MEMO, -oo);
		System.out.println(mat[0][0] + solve(0,1,0));
	}

	private static long solve(int row, int mask, int col) {
		if(col==N-1){
			if(row==2)return 0;
			else return -oo;
		}
		int hash = (row*(1<<3)+mask)*(N)+col;
		if(MEMO[hash]!=-oo)return MEMO[hash];
		long sol = -oo;
		for(int i=0;i<3;i++){
			for (int j=0;j<adj[row][i].length;j++){
				int m = adj[row][i][j];
				if((m&mask)!=(1<<row))continue;
				long sum = 0;
				int ii = 0;
				for(int y=0;y<2;y++){
					for(int x=0;x<3;x++){
						if(ii==row){
							ii++;
							continue;
						}
						sum+=(((1<<(ii++))&m)!=0)?mat[x][col+y]:0;
					}
				}
				sol = Math.max(sol, sum+solve(i,m>>3,col+1));
			}
		}
		return MEMO[hash] = sol;
	}
	

	private static class Jolty{
		static final int BASE_SPEED = 130;
		static final int BUFFER_SIZE = 1<<16;
		static final char NULL_CHAR = (char)-1;
		
		BufferedInputStream in;
		StringBuilder str = new StringBuilder();
		byte[] buffer = new byte[BUFFER_SIZE];
		
		char c = NULL_CHAR;
		int bufferIdx = 0, size = 0;
		
		public Jolty(InputStream in) {
			this.in = new BufferedInputStream(in,BUFFER_SIZE);
		}
		public int nextInt() {return (int)nextLong();}
		public double nextDouble() {return Double.parseDouble(next());}
		public long nextLong() {
			long negative = 0, res = 0;
			if(c==NULL_CHAR)c=nextChar();
			for(;(c<'0'||c>'9');c=nextChar())
				negative = (c=='-')?1:0;
			for(;c>='0'&&c<='9';c=nextChar())
				res = (res<<3)+(res<<1)+c-'0';
			return negative==1 ? -res : res;
		}
		
		public String nextLine() {
			str.setLength(0);
			for(c = c == NULL_CHAR ? nextChar() : c; c!='\n'; c= nextChar())
				str.append(c);
			c = NULL_CHAR;
			return str.toString();
		}
		public String next() {
			for(c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c);)
				c = nextChar();
			str.setLength(0);
			for(;!Character.isWhitespace(c);c=nextChar())
				str.append(c);
			return str.toString();
		}
		public char nextChar() {
			while(bufferIdx == size) {
				try{
					size = in.read(buffer);
					if(size == -1)throw new Exception();
				} catch (Exception e){}
				if(size == -1)size = BUFFER_SIZE;
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}
	}
}