Problem Description

As shown in the figure below, this is a honeycomb graph with side length $3$, and each point has a weight:

Now you need to go from some point in the top row to some point in the bottom row. Each move can only go to the lower-left point or the lower-right point. You may swap the values of two points in at most one selected row.

Find the maximum possible sum of point weights along a path from the top row to the bottom row after performing the swap.

Input Format

The first line contains an integer $n$, representing the side length of the honeycomb graph.
The next $2n-1$ lines contain several integers per line, describing the honeycomb graph.

Output Format

Output one integer on one line, representing the answer.

3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4

22

Hint

Sample Explanation

For sample $1$, swap $5$ and $1$ in the fourth row, and then we can obtain a path with the maximum sum of point weights:

The maximum value is $22$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 99$, and $0 \le$ each value in the honeycomb graph $\le 99$.

Note

Translated from BalticOI 2000 Day1 A Honeycomb Problem。

Translated by ChatGPT 5