宝石排列
时间限制：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 0jewel.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 0jewel.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$；
