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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.Collection;
import java.util.Set;
import java.util.TreeSet;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    static long INF = Long.MAX_VALUE >> 1;
    int n;
    int[][] a;
    long[][] sum;
    long[][] dp;
    static int WIDTH = 2;
    boolean[][] mark = new boolean[3][WIDTH];
    Set<Integer>[][][] maskSet = new Set[3][3][WIDTH];
    IntArrayList[][][] masks = new IntArrayList[3][3][WIDTH];

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      for (int start = 0; start < 3; ++start)
        for (int end = 0; end < 3; ++end) {
          for (int width = 0; width < WIDTH; ++width) {
            maskSet[start][end][width] = new TreeSet<>();
          }
        }
      for (int width = 1; width <= WIDTH; ++width) {
        generate(width);
      }
      n = in.nextInt();
      a = new int[3][n];
      for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j) {
          a[i][j] = in.nextInt();
        }
      sum = new long[8][n];
      for (int j = 0; j < n; ++j) {
        for (int mask = 0; mask < 8; ++mask) {
          sum[mask][j] = 0;
          for (int i = 0; i < 3; ++i)
            if ((mask & (1 << i)) > 0) {
              sum[mask][j] += a[i][j];
            }
        }
      }
      dp = new long[4][3];
      int t = 0;
      Arrays.fill(dp[t], -INF);
      Arrays.fill(dp[t + 1], -INF);
      dp[t][0] = 0;
      for (int i = 0; i < n; ++i) {
        Arrays.fill(dp[(t + 2) & 3], -INF);
        for (int width = 0; width < WIDTH; ++width)
          if (i + width < n) {
            int nxtT = (t + width + 1) & 3;
            for (int start = 0; start < 3; ++start)
              for (int end = 0; end < 3; ++end) {
                IntArrayList currentMasks = masks[start][end][width];
                for (int maskIdx = 0; maskIdx < currentMasks.size; ++maskIdx) {
                  int mask = currentMasks.get(maskIdx);
                  long currentSum = 0;
                  for (int j = 0; j <= width; ++j) {
                    currentSum += sum[(mask >> (j * 3)) & 7][i + j];
                  }
                  dp[nxtT][end] = Math.max(dp[nxtT][end], dp[t][start] + currentSum);
                }
              }
          }
        t = (t + 1) & 3;
      }
      out.println(dp[t][2]);
    }

    void generate(int width) {
      for (int start = 0; start < 3; ++start) {
        for (int x = 0; x < 3; ++x) {
          Arrays.fill(mark[x], false);
        }
        dfs(start, 0, start, width, 0);
      }
      for (int start = 0; start < 3; ++start)
        for (int end = 0; end < 3; ++end) {
          masks[start][end][width - 1] = new IntArrayList(maskSet[start][end][width - 1]);
        }
    }

    void dfs(int x, int y, int start, int width, int mask) {
      if (y == width) {
        maskSet[start][x][width - 1].add(mask);
        return;
      }
      if (x < 0 || x >= 3 || y < 0 || mark[x][y]) return;
      mark[x][y] = true;
      mask |= 1 << (y * 3 + x);
      dfs(x - 1, y, start, width, mask);
      dfs(x + 1, y, start, width, mask);
      dfs(x, y - 1, start, width, mask);
      dfs(x, y + 1, start, width, mask);
      mark[x][y] = false;
    }

  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

  }

  static interface IntCollection {
  }

  static class IntArrayUtils {
    public static String toString(int[] values, int fromIdx, int toIdx) {
      StringBuilder sb = new StringBuilder("[");
      for (int i = fromIdx; i < toIdx; ++i) {
        if (i != fromIdx) sb.append(", ");
        sb.append(values[i]);
      }
      return sb.append("]").toString();
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class IntArrayList implements IntCollection {
    private static final int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[IntUtils.nextPow2(capacity)];
      clear();
    }

    public IntArrayList(Collection<Integer> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public void addAll(Collection<Integer> values) {
      ensureCapacity(size + values.size());
      for (int value : values) {
        addInternal(value);
      }
    }

    public int get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }


    public String toString() {
      return IntArrayUtils.toString(values, 0, size);
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      int[] newValues = new int[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }

    private void addInternal(int value) {
      values[size++] = value;
    }

  }
}

