时间限制：1秒　　内存限制：256M

---

【问题描述】

　　光光家住在农村，离他的家不远有一口井，传说是光光的祖先开掘的。虽然光光的村里通了自来水，但是由于这口井井水质量非常的好，因此光光仍然喝这口井里的水。光光非常喜欢这口井，所以他经常去打水。

　　光光的家里有 \(n\) (\(n\) 是偶数)只桶，这些桶虽然大小相等，但由于很多都有些破损，所以认为他们是不同的。光光经常挑一根扁担（带两只空桶，必须是空的，且是 2 只）去井边打水。光光每次去井边都会把桶中的水装到极限（假设水量无穷，且光光都能够担得动）。设光光挑得是 \(x,y\) 两只桶，则打水一趟需要走 \(a[x,y]\) 分钟。

　　光光想要在最少的时间内用自己的力量把家里所有的空桶装满。光光觉得这是个难题，于是来找你帮忙。

【输入格式】

　　第一行一个数字 \(n\)；
接下来 \(n\) 行，每行 \(n\) 个数字，\(a\) 矩阵中每一个数都是正整数，且 \(a[i,i]\) 是没用的。（保证有 \(a[i,j]=a[j,i]\)）
　　注意：迷宫的行号和列号编号都是从 1 开始的。

【输出格式】

　　仅包含一行，就是最佳挑水方案的最少时间。

【输入输出样例1】

　Input

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

　Output

16

【数据说明】

　　对于 \(50\%\) 的数据保证 \(n≤10\)。
　　对于 \(50\%\) 的数据保证 \(n≤24\)，\(a[i][j]<=10 000 000\)。

【来源】

　　Mr.he