题目描述

Glad 发现了一个 $n$ 层数字三角形，他发现可以用魔法来操纵这个三角形！

他可以先消耗 $nk_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\circ$。

然后，他可以不停地进行下面操作：

• 消耗 $1$ 点消耗值，选择一层，调换这一层任意两个数的位置。

现在，Glad 要从三角形的最后一层走到最顶层，起点可以为最后一层的任意一个数，行走的每一步只能走到与当前数相邻的数上，且每一行只能经过一个数。

Glad 想在经过数之和最大的前提下让消耗的消耗值最小，你可以帮帮他吗？

输入格式

一个正整数 $n$，表示三角形的层数。

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

输出格式

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

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

40 10

提示

【样例解释】

初始三角形为：

    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$ 点调换值。

【数据范围】

本题采用捆绑测试。

特殊性质 A：不需要调换数字就可以得到最优解。

特殊性质 B：不需要向右旋转就可以得到最优解。

对于 $100\%$ 的数据，保证：$1\leqslant n\leqslant 10^3$，$0\leqslant a_i\leqslant10^4$。

【工作人员】