Honeycomb Maximum Route Sum

Time limit1sMemory limit128 MB

Summary

Find the maximum sum path through a hexagonal grid moving diagonally down-left or down-right, allowing one row to have its maximum value moved to any position once.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Greedy
Solved: No attempts yet

Problem

Figure 1 shows a honeycomb of numbers (the side length of the honeycomb is 3). A route starts from some node in the uppermost row and ends at some node in the lowest row. From a node, the route can continue only diagonally down to the left or diagonally down to the right. When creating a route through the honeycomb, you may perform at most one swap of two numbers on at most one horizontal row. (Swapping means that, in one chosen row, you may move the greatest number of that row to any position on the same row.) Write a program that computes the highest possible sum of the numbers on a route, using this ability to swap two numbers on a chosen row.

Figure 1. A honeycomb of side length 3.

Input

The first line contains the side length n of the honeycomb. The honeycomb consists of 2n − 1 horizontal rows. The next 2n − 1 lines contain the numbers of each row, from top to bottom, separated by spaces. The i-th row from the top (1 ≤ i ≤ n) contains n + i − 1 numbers; after the middle row the count decreases by one per line, so the bottom row again contains n numbers.

Output

Print the highest sum as a single integer.

Constraints

Each number in a node is an integer between 0 and 99.
The side length of the honeycomb is an integer between 1 and 99.

Hint

In Figure 1 the nodes of the correct solution (3 + 2 + 8 + 5 + 4 = 22) are shaded gray. Note that the number '5' on the 4th row (from the top) is moved to the 3rd position (from the left) on that row.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
2
1 2
3 4 5
6 7
```
Expected output
```
14
```