P7266 [BalticOI 2000] Honeycomb Problem

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.

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 one integer on one line, representing the answer.

#### 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: $$3 \to 2 \to 8 \to 5 \to 4$$ 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](https://boi.cses.fi/files/boi2000_day1.pdf)。 Translated by ChatGPT 5