该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个 $n$ 层数字三角形，可以用魔法来操纵这个三角形。

• 消耗 $n\times k_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\circ$。

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

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

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

在经过数之和最大的前提下让消耗的消耗值最小，你可以解决这个问题吗？

输入格式

一个正整数 $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$。