暂无测试数据。

为了保持良好的身体素质，蒜头君每天都会到健身房进行健身训练。蒜头君每天会按照某种顺序依次进行 $N$ 个训练项目，编号分别为 $1,2,3,...,N$。

已知不同的训练顺序会影响训练的效果，现在蒜头君将训练项目进行量化（用数字表示训练效果，数字越大表示训练效果越好）。当项目 $i$ 被安排在项目 $j$ 之前进行训练时，项目 $i$ 可以获得的训练效果是 $a_{i,j}$。

为了使蒜头君的训练效果尽可能的好，请你帮助蒜头君确定训练的顺序，使得他可以通过这 $\frac{N(N-1)}{2}$ 对训练项目获得的训练效果之和最大。

假设训练顺序为 $1,3,2$，那么这 $\frac{N(N-1)}{2} = \frac{3\times 2}{2} = 3$ 对训练项目是指：$(1,3), (1,2),(3,2)$。

输入格式

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

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

输出格式

输出一个整数表示最大的训练效果之和。

数据规模

• 对于 $40\%$ 的数据：$2\leq N\leq 8$；
• 对于 $70\%$ 的数据：$2\leq N\leq 15$；
• 对于 $100\%$ 的数据：$2\leq N\leq 20,0\leq a_{i,j}\leq 10000$。

3
0 2 4
3 0 2
1 3 0

9

3
0 5 3
4 0 10
12 4 0

26