Maximum Path Sum with Minimal Consumption

Glad found an n-layer number triangle. He can use magic to manipulate the triangle in two ways:

• First, he may spend \(n\,k_1\) consumption points to rotate the triangle \(k_1\) times. Each "rotation" means a clockwise rotation of \(120^\circ\) about the triangle’s center. Note that performing 3 rotations returns the triangle to its original orientation, so effectively only 0, 1, or 2 rotations are useful.
• Then, he may perform the following operation any number of times (each costing 1 consumption point): choose a layer and swap the positions of any two numbers in that layer.

After performing these operations, Glad will travel from the bottom layer to the top layer. He may choose any number in the bottom layer as his starting point. In each step he moves from a number in the current row to an adjacent number in the next row up (where adjacent means that if, after reordering the row by magic, the row is viewed as a 1-indexed array, then from index \(j\) one can move only to index \(j\) or \(j-1\) in the row above). Note that each row can contribute only one number.

Glad wants to achieve the maximum possible sum along his path. Since the maximum sum is predetermined (namely, the sum of the maximum numbers of each row), his goal is to minimize the total consumption spent (both on rotations and swaps) under the constraint that the path collects the maximum number from every row. In each row, if the maximum number is not already in the position required to keep the path contiguous then Glad can perform a swap (costing 1) to bring it there. Additionally, a rotation operation reorders every row. For the purpose of this problem, assume that the triangle has three orientations determined by rotations:

• Orientation 0 (no rotation): The rows remain as given. That is, row \(i\) is \([a_1, a_2, \dots, a_i]\).
• Orientation 1 (one rotation): Each row is cyclically shifted so that the last element becomes the first element. For row \(i\), the order becomes \([a_i, a_1, a_2, \dots, a_{i-1}]\).
• Orientation 2 (two rotations): Each row is cyclically shifted in the opposite direction; for row \(i\), the order becomes \([a_2, a_3, \dots, a_i, a_1]\).

For each orientation, Glad can reassign (via swaps at cost 1 per row if needed) the maximum number of that row to a position that makes the contiguous (adjacent) path possible. Traveling from the top row downwards (which is equivalent to going upwards from the bottom row), the allowed moves in the triangle (when viewed as a 1-indexed array in the current orientation) are as follows: if you are at position \(j\) in the current row, then in the next row you may only choose the number at position \(j\) or \(j+1\>.

Your task is to help Glad by computing the minimum total consumption (including both the rotation cost and the swap costs) required so that he can achieve the maximum possible sum, which is the sum of the maximum number in each row.

Note: The rotation cost is \(n\) per rotation. That is, if you perform \(k_1\) rotations then the rotation cost is \(n\cdot k_1\). For the swaps, in each row, if the maximum number is already in the chosen position then no swap is required (cost 0), otherwise one swap (cost 1) is needed for that row.

inputFormat

The first line contains a single integer \(n\) (the number of rows of the triangle). Each of the following \(n\) lines contains the numbers in that row. The \(i\)th row contains \(i\) integers separated by spaces.

outputFormat

Output a single integer representing the minimum total consumption (the sum of the rotation cost and the swap costs) required so that Glad can obtain a path that collects the maximum numbers from every row.

sample

1
5

0