说明

在AC王国里，AC这个王国里有n个城市，tpz是一个高级工程师，某一天他受命去用最短的线去建造电缆来连接这个王国里所有的城市(只要俩个城市俩俩之间可以任意到达就行了)。他测量了每个城市到其他城市的距离，并用n*n的矩阵表示出来，但在矩阵的对角线上他用了一个随机的数随便表示了自己到自己的距离。这个王国城市有点多，而且时间紧迫，他一下子慌了，于是求你来帮他连接这个n个城市。

输入格式

第一行输入一个数字n，代表城市的个数,2<=n<=100.第二行输入一个n行n列的矩阵a，代表第i个城市到第j个城市的距离dis,0<=dis<=1e10.

输出格式

输出一个整数,表示最短的电缆的长度.

样例

4
0 3 4 7
3 0 7 4
3 3 0 3
4 4 0 4

6

提示

注意：对角线上的数字。