Description

对于一张有向图，定义 d(u,v,w)为从u号点出发，不经v号点，最终到达w号点的最短路径长度。如果不存在这样的路径，d(u,v,w)的值为−1。
你也可以认为 d(u,v,w) 是删去 v点和其相关的边后，图中 u 到 w的最短路。

现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为−1），对于所有满足 1≤x,y,z≤n,x≠y,y≠z的有序数对 (x,y,z)，求它们d(x,y,z) 的和。

你可以借助样例一解释来理解上面这句话的意思。

Format

Input

第一行输入一个正整数n，表示该地区的点数。
接下来输入n行，每行输入n个整数。第i行第j个数 Gi,j表示从i号点到j号的有向路径长度。如果这个数为−1，则表示不存在从 i号点出发到j号点的路径。

Output

输出一个整数表示答案。

Sample 1

Input

3
0 1 -1
100 0 2
-1 -1 0

Output

100

Sample 2

Input

4
0 1 -1 -1
-1 0 1 -1
-1 -1 0 1
1 -1 -1 0

Output

4

Limitation

2s, 512MiB for each test case.