[问题描述]

光光住在农村，离他的家不远有一口井，传说是光光的祖先开掘的。虽然光光的村子里通了自来水，但是由于这口井井水质量非常的好，因此光光仍然喝这口井里的水。光光非常喜欢这口井，所以他经常去打水。 光光的家里有 n（n 是偶数）只桶，这些桶虽然大小相等，但是由于很多都有些破损，所以认为它们是不同的。光光经常挑一根扁担（带两只空桶，必须是空的，且是 2 只）去井边打水。光光每次去井旁都会把桶中的水装到极限（假设水量无穷，且光光都能够担得动）。设光光挑得是x、y 两只桶，则打水一趟需要走 time[x,y]分钟。 光光想要在最少的时间内用自己的力量把家里所有的空桶装满。光光觉得这是个难题，于是来找你帮忙。

[输入]

输入文件 spring.in包含以下内容：

第一行有一个数字，是n。 接下来n 行，每行 n 个数字，代表了 time 矩阵。time 矩阵中每一个数都是正 整数，且time 矩阵中 time[i,i]是没有用的。 （注意：time[i,j]=time[j,i]）

[输出]

输出文件spring.out 仅包含一行，就是最佳挑水方案的最少时间。

[样例输入]

4 
0 100 5 100 
100 0 100 11 
5 100 0 100 
100 11 100 0 

[样例输出]

16 

[数据规模约定]

100%的数据中，time 矩阵中的每一个数字小于等于32768。

100%的数据中，n>=4；

40%的数据中，n<=12；

100%的数据中，n<=18。