Description

杜王町为了使居民串门方便进行了新一轮的城镇规划，在新一轮规划之后每两户都存在一条路径。而秋葵是杜王町的一个邮递员，每一天都要给每户送信，而每户所收的信为一封，秋葵如何送信才能使得所经过的路径最短呢？

Input

第一行输入一个整数n。
接下来n个整数，其中第i行第j个整数表示点i到点j的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

Output

输出一个整数，表示最短路径的长度。

Format

1≤n≤20
0≤a[i,j]≤10^7
(1s/64mb)

Input Example

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

Output Example

18