Maximum Path Sum in a Honeycomb with One Swap

You are given a honeycomb grid with side length \( n \). The honeycomb is arranged in \( 2n-1 \) rows. The first \( n \) rows have increasing numbers of points: the first row has \( n \) points, the second row has \( n+1 \) points, and so on, until the \( n\)-th row which has \( 2n-1 \) points. Then the grid has \( n-1 \) more rows with decreasing counts: the \((n+1)\)-th row has \( 2n-2 \) points, the next row has \( 2n-3 \) points, and the last row has \( n \) points.

Each point is assigned an integer weight. You must choose a starting point from the top row and a destination point from the bottom row, and then determine a path moving downward. From any point, you are allowed to move only to the two points in the next row that are in the left‐down and right‐down positions. More specifically, if we index rows from \( 0 \) to \( 2n-2 \) and number the columns in each row from \( 0 \) (from left to right), then the moves are defined as follows:

• For the first \( n-1 \) rows (the increasing part), from row \( i \) and column \( j \) you may move to row \( i+1 \), column \( j \) or \( j+1 \).
• For the remaining rows (the decreasing part), from row \( i \) and column \( j \) you may move to row \( i+1 \), column \( j-1 \) (if it exists) or column \( j \) (if it exists).

In addition, you are allowed to choose at most one row in which you may swap the values of any two points. This swap is performed before proceeding with the path. Effectively, if you use the swap on a row, you can always ensure that the point you pass through in that row has the maximum value of that row.

Your task is to calculate the maximum possible sum of the weights along any valid downward path from the top row to the bottom row after performing at most one swap operation.

inputFormat

The input begins with a single integer \( n \) (with \( n \ge 3 \)), which represents the side length of the honeycomb. Following this, there are \( 2n-1 \) lines. The first \( n \) lines represent the increasing part of the honeycomb: the \( i\)-th line (1-based) contains \( n+i-1 \) integers. The following \( n-1 \) lines represent the decreasing part: the \( j\)-th of these lines contains \( 2n-1-j \) integers.

All integers are separated by spaces.

outputFormat

Output a single integer, which is the maximum sum that can be obtained along a valid path from the top row to the bottom row after performing at most one swap operation.

sample

3
1 2 3
4 5 6 7
8 9 10 11 12
13 14 15 16
17 18 19

57