宝石排列

时间限制：1秒，内存限制：128MB

读入文件名：jewel.in

输出文件名：jewel.out

【题目描述】

巫师手中有$n$个宝石，编号从1到$n$，他要将这些宝石排成一列，相邻的宝石之间有共同作用，产生魔力。

已知任意两个宝石相邻会产生的魔力值，即若第$i$个宝石和第$j$个宝石相邻，则会产生$a_{i,j}$的魔力。宝石排列的魔力值为所有相邻宝石之间产生的魔力值之和。

问将$n$个宝石排成一列最多能产生多少魔力值。

【输入格式】

输入有$n+1$行，第一行为一个正整数$n$，表示宝石的个数。

接下来是$n$行$n$列的整数矩阵，其中第$i$行第$j$列表示$a_{i,j}$，行内数据间用一个空格分隔。

保证$a_{i,j}=a_{j,i}$，且$a_{i,i}=0$。

【输出格式】

输出一行，包含一个正整数，表示最多能产生的魔力值。

【输入输出样例1】

jewel.in

5
0 1 2 3 4
1 0 2 3 4
2 2 0 3 4
3 3 3 0 4
4 4 4 4 0

jewel.out

14

【输入输出样例2】

jewel.in

5
0 6 2 6 10 
6 0 7 10 1 
2 7 0 2 1 
6 10 2 0 9 
10 1 1 9 0

jewel.out

36

【数据规模与约定】

对于前30%的数据，$0\le a_{i,j}\le 10000$；

对于前80%的数据，$1\le n\le 10$；

对于100%的数据，$1\le n\le 16$，$0\le a_{i,j}\le 10^9$；