P9541 「AWOI Round 2 D」数字三角形

Glad 发现了一个 $n$ 层数字三角形，他发现可以用魔法来操纵这个三角形！ 他可以先消耗 $nk_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\circ$。 然后，他可以不停地进行下面操作： - 消耗 $1$ 点消耗值，选择一层，调换这一层任意两个数的位置。 现在，Glad 要从三角形的最后一层走到最顶层，起点可以为最后一层的任意一个数，行走的每一步只能走到与当前数相邻的数上，且每一行只能经过一个数。 Glad 想在经过数之和最大的前提下让消耗的消耗值最小，你可以帮帮他吗？

一个正整数 $n$，表示三角形的层数。 后面 $n$ 行，表示数字三角形。其中第 $i$ 层有 $i$ 个数（$1\leqslant i\leqslant n$）。

两个整数，分别表示最大能经过的数之和以及最少要消耗多少消耗值。

**【样例解释】** 初始三角形为： ``` 1 2 3 4 5 6 10 9 8 7 2 5 2 5 6 ``` 将其向右翻转 $2$ 次，消耗 $10$ 点调换值，此时三角形变为： ``` 6 7 5 6 8 2 3 5 9 5 1 2 4 10 2 ``` 无须调换数字，沿着 $6,7,8,9,10$ 走，可以得到最大值 $40$，共耗费 $10$ 点调换值。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 数据范围 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | | $\text{Subtask1}$ | $1\leqslant n\leqslant 10$ | AB | $10$ | | $\text{Subtask2}$ | $1\leqslant n \leqslant 10$ | A | $10$ | | $\text{Subtask3}$ | $1\leqslant n \leqslant 10$ | B | $10$ | | $\text{Subtask4}$ | $1\leqslant n \leqslant 10$ | 无 | $10$ | | $\text{Subtask5}$ | $1\leqslant n \leqslant 40$ | 无 | $20$ | | $\text{Subtask6}$ | $1\leqslant n\leqslant 10^3$ | 无 | $40$ | 特殊性质 A：不需要调换数字就可以得到最优解。 特殊性质 B：不需要向右旋转就可以得到最优解。 对于 $100\%$ 的数据，保证：$1\leqslant n\leqslant 10^3$，$0\leqslant a_i\leqslant10^4$。 **【工作人员】** | $\text{Idea}$ | $\text{Data}$ | $\text{Check}$ | $\text{Solution}$ | | :----------: | :----------: | :----------: | :----------: | |[S__X](/user/310466) |[S__X](/user/310466)|[I_am_AKed_by_NOI](/user/807853) | [I_am_AKed_by_NOI](/user/807853) |