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

题目描述

众所周知，大部分游戏的装备系统中都存在一个子系统——附魔

hcr 玩游戏的时候总是有一些强迫症，一定要把材料花费在最好的装备上

这天他终于获得了一件毕业武器，以后再也不用换武器了！

于是他决定把从 $1$ 级开始囤到现在的所有材料统统附魔在这把武器上

hcr 总共囤了 $n$ 件附魔材料，编号分别为 $1,2,3 \dots n$

因为附魔材料之间会互相影响，所以 hcr 每次附魔只能使用一件附魔材料，而后面附魔的材料可能会在一定程度上影响已经附魔的材料，使其效果发生变化

hcr 查询了各种资料，最后得到了一张表格 $G$

其中 $G[i][j]$ 表示当 $j$ 号材料附魔时，如果 $i$ 已经被附魔在装备上了，那么 $i$ 号材料的战斗力将额外增加 $G[i][j]$

现在 hcr 想知道，怎么安排附魔顺序可以使得附魔额外增加的战斗力最大？

输入格式

输入第一行包含一个正整数 $N$。

接下来 $N$ 行每行包含 $N$ 个整数，其中第 $i$ 行的第 $j$ 个数表示 $G_{i,j}$，数据保证 $G_{i,i}=0$。

输出格式

输出一个整数表示额外增加的最大战斗力值。

数据规模

对于 $40\%$ 的数据：$2\leq N\leq 8$；

对于 $70\%$ 的数据：$2\leq N\leq 15$；

对于 $100\%$ 的数据：$2\leq N\leq 20,0\leq G_{i,j} \leq 10000$。

样例输入

3
0 2 4
3 0 2
1 3 0

样例输出

9

样例解释

附魔顺序为 $1,3,2$，最终 $1$ 号材料额外增加 $2 + 4$ 点战斗力，$3$ 号材料额外增加 $3$ 点战斗力 最大总共额外增加 $2 + 4 + 3 = 9$ 点战斗力