Problem Description

Glad found a number triangle with $n$ layers. He found that he can use magic to manipulate this triangle.

First, he can spend $n k_1$ cost points to rotate the triangle $k_1$ times. Here, a “rotation” means rotating $120^\circ$ clockwise around the center of the triangle.

Then, he can repeatedly perform the following operation:

• Spend $1$ cost point, choose one layer, and swap the positions of any two numbers in that layer.

Now, Glad wants to walk from the last layer of the triangle to the very top. The starting point can be any number in the last layer. Each step can only move to a number adjacent to the current number, and in each row he can pass through at most one number.

Glad wants to minimize the total cost points consumed under the condition that the sum of the numbers he passes through is maximized. Can you help him?

Input Format

A positive integer $n$, representing the number of layers of the triangle.

The next $n$ lines describe the number triangle. The $i$-th layer has $i$ numbers ($1\leqslant i\leqslant n$).

Output Format

Two integers, representing the maximum possible sum of the numbers that can be passed through, and the minimum total cost points that must be spent.

5
1
2 3
4 5 6
10 9 8 7
2 5 2 5 6

40 10

Hint

Sample Explanation

The initial triangle is:

    1
   2 3
  4 5 6
10 9 8 7
2 5 2 5 6

Rotate it to the right $2$ times, costing $10$ cost points. The triangle becomes:

    6
   7 5
  6 8 2
 3 5 9 5
1 2 4 10 2

Without any swaps, walking along $6,7,8,9,10$ yields the maximum value $40$, and the total cost is $10$ cost points.

Constraints

This problem uses bundled testdata.

Special Property A: An optimal solution can be obtained without swapping numbers.

Special Property B: An optimal solution can be obtained without rotating to the right.

For $100\%$ of the testdata, it is guaranteed that $1\leqslant n\leqslant 10^3$ and $0\leqslant a_i\leqslant10^4$.

Staff

Translated by ChatGPT 5