Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

d = M//N
while d >= 1:
    if M%d == 0:
        print(d)
        break
    else:
        d -= 1

Fixed submission:
N,M = map(int,input().split())

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

for i in reversed(range(1,M//N+2)):
    if M%i == 0 and M//i >= N:
        print(i)
        break

Fixed submission:
N,M = map(int,input().split())

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

def div(x):
    div_list = []
    for i in range(1,x//N+2):
        if x%i == 0 and x//i >= N:
            div_list.append(i)
    return div_list

a = div(M)
print(a[-1])

Fixed submission:
N,M = map(int,input().split())

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break
Buggy python submission (verdict: Runtime Error):
from corections import Counter 
n = int(input())
v = list(map(int,input().split()))
 
odd = []
even = []
for i in range(n//2):
	odd.append(v[2*i+1])
	even.append(v[2*i])
 
odd = sorted(odd)
even = sorted(even)
ac = Counter(odd).most_common(2)
bc = Counter(even).most_common(2)
def cnt(X):
	count = 0
	ans = 0
	for i in range(len(X)-1):
		if X[i+1] == X[i]:
			count += 1
			ans = max(ans,count)
		else:
			count = 0
	return ans+1
            
if ac[0][0] != bc[0][0]:
  print(len(v)-cnt(odd)-cnt(even))
elif len(ac) == 1 and len(bc) == 1:
	print(n//2)
else:
	print(n-max(ac[0][1]+bc[1][1],ac[1][1]+bc[0][1]))

Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Buggy python submission (verdict: Runtime Error):
s = input()
 
ss = ""
for i in s:
  if s[i] == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)


Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Buggy python submission (verdict: Runtime Error):
s = input()
 
ss = ""
for i in s:
  if s == "1"
  		ss += "9"	
  else:
    	ss += "1"
    
print(ss)

Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Buggy python submission (verdict: Runtime Error):
s = input()
 
ss = ""
for i in s:
  if s == "1"
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Buggy python submission (verdict: Runtime Error):
s = input()
 
ss = ""
for i in range(len(s)):
  if s[i] == "1"
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Buggy python submission (verdict: Runtime Error):
s = input()

ss = ""
for i in range(len(S)):
  if s[i] == "1"
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)

Fixed submission:
s = input()
 
ss = ""
for i in s:
  if i == "1":
  	ss += "9"	
  else:
    ss += "1"
    
print(ss)
Buggy python submission (verdict: Runtime Error):
from corections import Counter 
n = int(input())
v = list(map(int,input().split()))
 
odd = []
even = []
for i in range(n//2):
	odd.append(v[2*i+1])
	even.append(v[2*i])
 
odd = sorted(odd)
even = sorted(even)
ac = Counter(odd).most_common(2)
bc = Counter(even).most_common(2)
def cnt(X):
	count = 0
	ans = 0
	for i in range(len(X)-1):
		if X[i+1] == X[i]:
			count += 1
			ans = max(ans,count)
		else:
			count = 0
	return ans+1
            
if ac[0][0] != bc[0][0]:
  print(len(v)-cnt(odd)-cnt(even))
elif len(ac) == 1 and len(bc) == 1:
	print(n//2)
else:
	print(n-max(ac[0][1]+bc[1][1],ac[1][1]+bc[0][1]))

Fixed submission:
from collections import Counter 
n = int(input())
v = list(map(int,input().split()))
 
odd = []
even = []
for i in range(n//2):
	odd.append(v[2*i+1])
	even.append(v[2*i])

odd = sorted(odd)
even = sorted(even)
ac = Counter(odd).most_common(2)
bc = Counter(even).most_common(2)
def cnt(X):
	count = 0
	ans = 0
	for i in range(len(X)-1):
		if X[i+1] == X[i]:
			count += 1
			ans = max(ans,count)
		else:
			count = 0
	return ans+1
            
if ac[0][0] != bc[0][0]:
  print(len(v)-cnt(odd)-cnt(even))
elif len(ac) == 1 and len(bc) == 1:
	print(n//2)
else:
	print(n-max(ac[0][1]+bc[1][1],ac[1][1]+bc[0][1]))
Buggy python submission (verdict: Runtime Error):
a,b = map.(int,input().split())

if ( a * b ) % 2 == 0:
  print("No")
else:
  print("Yes")

Fixed submission:
a,b = map(int,input().split())
 
if ( a * b ) % 2 == 0:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N,M,Q = map(int,input().split())
    go = [[0 for _ in range(N)] for i in range(N)]
    for _ in range(M):
        L,R = map(int,input().split())
        go[L-1][R-1] += 1
        
    qu = []
    for _ in range(Q):
        p,q = map(int,input().split())
        qu.append((p-1,q-1))
        
    num = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        num[i][0] = go[i][0]
    for i in range(N):
        for j in range(N-1):
            num[i][j+1] = num[i][j] + go[i][j+1]
            
    for i in range(Q):
        ans = 0
        p,q = qu[i]
        for j in range(p,q+1):
            ans += num[j][q]
        print(ans)
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N,M,Q = map(int,input().split())
    go = [[0 for _ in range(N)] for i in range(N)]
    for _ in range(M):
        L,R = map(int,input().split())
        go[L-1][R-1] += 1
        
    qu = []
    for _ in range(Q):
        p,q = map(int,input().split())
        qu.append((p,q))
        
    num = [[0 for _ in range(N)] for _ in range(N)]
    _num = [[0 for _ in range(N)] for _ in range(N+1)]
    for i in range(N):
        num[i][0] = go[i][0]
    for i in range(N):
        for j in range(N-1):
            num[i][j+1] = num[i][j] + go[i][j+1]

    for i in range(N):
        for j in range(N):
            _num[j+1][i] = _num[j][i] + num[j][i]
            
    for i in range(Q):
        p,q = qu[i]
        ans = _num[q][q-1] - _num[p-1][q-1]
        print(ans)
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
from itertools import permutations

def main():
    N,C = map(int,input().split())
    D = [list(map(int,input().split())) for _ in range(C)]
    col = [list(map(int,input().split())) for _ in range(N)]
    
    mod_color = [[],[],[]]
    for i in range(N):
        for j in range(N):
            mod_color[(i+j)%3].append(col[i][j]-1)

    ans = 10**10
    for x,y,z in permutations(range(C),3):
        ret = 0
        for num in mod_color[0]:
            ret += D[num][x]
        for num in mod_color[1]:
            ret += D[num][y]
        for num in mod_color[2]:
            ret += D[num][z]
        ans = min(ans,ret)
        
    print(ans)
    
if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N,C = map(int,input().split())
    D = [list(map(int,input().split())) for _ in range(C)]
    c = [list(map(int,input().split())) for _ in range(N)]
    mod_0 = [0 for _ in range(C)]
    mod_1 = [0 for _ in range(C)]
    mod_2 = [0 for _ in range(C)]
    for i in range(N):
        for j in range(N):
            if (i+j)%3 == 0:
                mod_2[c[i][j]-1] += 1
            if (i+j)%3 == 1:
                mod_0[c[i][j]-1] += 1
            if (i+j)%3 == 2:
                mod_1[c[i][j]-1] += 1
    INF = 10**10
    ans = INF
    for i in range(C):
        for j in range(C):
            if i == j:
                continue
            for k in range(C):
                if i == k or j == k:
                    continue
                ans = min(ans,sum(mod_0[n]*D[n][i] for n in range(C))+\
                              sum(mod_1[n]*D[n][j] for n in range(C))+\
                              sum(mod_2[n]*D[n][k] for n in range(C)))
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

S = input()

ans = min(S.count("W"),S.count("E"))
for i in range(1,n):
	left = S[:i-1]
	right = S[i+1:]
	exans = left.count("W")+right.count("E")
	ans = min(ans,exans)

print(ans)

Fixed submission:
n = int(input())
S = input()

west = [0]*(n+2)
east = [0]*(n+2)
ans = 10**6
for i in range(1,n+1):
	if S[i-1] == "W":
		west[i] = west[i-1]+1
	else:
		west[i] = west[i-1]
	if S[-i] == "E":
		east[-i-1] = east[-i]+1
	else:
		east[-i-1] = east[-i]

for i in range(1,n+1):
	ans = min(ans,west[i-1]+east[i+1])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [0 for _ in range(N)]
    for i in range(N):
        A = int(input())
        ind[A-1] = i

    ans = 0
    count = 0
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            count += 1
        else:
            ans = max(ans,count)
            count = 0
        ans = max(ans,count)

    print(N-ans-1) 

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [0 for _ in range(N)]
    for i in range(N):
        A = int(input())
        ind[A-1] = i

    ans = 0
    count = 0
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            count += 1
        else:
            ans = max(ans,count)
            count = 0
        ans = max(ans,count)

    print(N-ans-1) 

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
#input = sys.stdin.readline

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s += s
    ans = 0
    for i in range(N):
        b = True
        for x in range(N):
            for y in range(x,N):
                if s[x+i][y] != s[y+i][x]:
                    b = False
        if b:
            ans += N
    
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
import sys
#input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s = np.array(s)
    ans = 0
    for i in range(N):
        T = np.vstack((s[i:],s[:i]))
        if np.all(T==T.T):
            ans += N
            
    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
#input = sys.stdin.readline

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s += s
    ans = 0
    for i in range(N):
        b = True
        for x in range(N):
            for y in range(N):
                if s[x+i][y] != s[y+i][x]:
                    b = False
        if b:
            ans += N
    
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
import sys
#input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s = np.array(s)
    ans = 0
    for i in range(N):
        T = np.vstack((s[i:],s[:i]))
        if np.all(T==T.T):
            ans += N
            
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = list(map(int,input().split()))

for i in range(N):
	Xwithout = X[:i]+X[i+1:]
	Xwithout.sort()
	print(Xwithout[N//2-1])

Fixed submission:
N = int(input())
X = list(map(int,input().split()))

mylist = sorted(X)
for i in range(N):
	ans = mylist[N//2-1]
	if X[i] > ans:
		print(ans)
	else:
		print(mylist[N//2])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    INF = 10**5
    maze_list = [[INF for _ in range(W)] for _ in range(H)]
    maze_list[0][0] = 0
    def item(array):
        return [item for sublist in array for item in sublist]

    counter = sorted(list(Counter(item(s)).items()))

    queue = []
    queue.insert(0,(0,0))
    while len(queue):
        x,y = queue.pop()
        if x == H-1 and y == W-1:
            break
        for i in range(4):
            nx,ny = x + [1,0,-1,0][i],y + [0,1,0,-1][i]
            if (0<=nx and nx<H and 0<=ny and ny<W):
                if (s[nx][ny]!="#" and maze_list[nx][ny]==INF):
                    queue.insert(0,(nx,ny))
                    maze_list[nx][ny] = maze_list[x][y] + 1

    if maze_list[H-1][W-1] == INF:
        print(-1)
    else:
        print(counter[1][1]-maze_list[H-1][W-1]-1)

if __name__ == "__main__":
    main()

Fixed submission:
from collections import Counter
def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    INF = 10**5
    maze_list = [[INF for _ in range(W)] for _ in range(H)]
    maze_list[0][0] = 0
    def item(array):
        return [item for sublist in array for item in sublist]

    counter = list(Counter(item(s)).items())
    num = 0
    for i in range(len(counter)):
        if counter[i][0] == ".":
            num = counter[i][1]
            break

    queue = []
    queue.insert(0,(0,0))
    while len(queue):
        x,y = queue.pop()
        if x == H-1 and y == W-1:
            break
        for i in range(4):
            nx,ny = x + [1,0,-1,0][i],y + [0,1,0,-1][i]
            if (0<=nx and nx<H and 0<=ny and ny<W and \
                s[nx][ny]!="#" and maze_list[nx][ny]==INF):
                queue.insert(0,(nx,ny))
                maze_list[nx][ny] = maze_list[x][y] + 1

    if maze_list[H-1][W-1] == INF:
        print(-1)
    else:
        print(num-maze_list[H-1][W-1]-1)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    left = 0
    right = N
    print(left,flush=True)
    ls = int(input())
    if ls == "Vacant":
        exit()
        
    while right-left > 1:
        mid = (right+left)//2
        print(mid,flush=True)
        nls = input()
        if get == "Vacant":
            exit()
        if nls == ls:
            if (mid-left)%2 == 0:
                left = mid
            else:
                right = mid
        else:
            if (mid-left)%2 == 1:
                left = mid
                ls = nls
            else:
                right = mid

if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    left = 0
    right = N
    print(left,flush=True)
    ls = input()
    if ls == "Vacant":
        exit()
        
    while right-left > 1:
        mid = (right+left)//2
        print(mid,flush=True)
        nls = input()
        if nls == "Vacant":
            exit()
        if nls == ls:
            if (mid-left)%2 == 0:
                left = mid
            else:
                right = mid
        else:
            if (mid-left)%2 == 1:
                left = mid
                ls = nls
            else:
                right = mid

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

X = [list(map(int,input().split())) for _ in range(N-1)]

def leave(a,b,c):
	while a>b:
		b += c
	return b

for j in range(N-1):
	time = 0
	for i in range(j,N-1):
		if time <= X[i][1]:
			time = X[i][0]+X[i][1]
		else:
			time = leave(time,X[i][1],X[i][2])+X[i][0]
	print(time)
print(0)

Fixed submission:
N = int(input())

X = [list(map(int,input().split())) for _ in range(N-1)]


for j in range(N-1):
	time = 0	
	for i in range(j,N-1):
		if time <= X[i][1]:
			time = X[i][0]+X[i][1]
		elif (time-X[i][1])%X[i][2] == 0:
			time += X[i][0]
		else:
			time += X[i][0]+(X[i][2]-(time-X[i][1])%X[i][2])
	print(time)
print(0)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline
import sympy

def main():
    N = int(input())
    M = 100000
    def sieve(n):
        is_prime = [True for _ in range(n+1)]
        is_prime[0] = False

        for i in range(2, n+1):
            if is_prime[i-1]:
                j = 2 * i
                while j <= n:
                    is_prime[j-1] = False
                    j += i
        return is_prime
    prime = sieve(M)
    alike = [0]
    for i in range(1,M+1,2):
        if (prime[i-1] and prime[(i+1)//2-1]):
            alike.append(alike[-1]+1)
        else:
            alike.append(alike[-1])
            
    for i in range(N):
        l,r = map(int,input().split())
        l = (l+1)//2
        r = (r+1)//2
        print(alike[r]-alike[l-1])
    
    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    M = 100000
    def sieve(n):
        is_prime = [True for _ in range(n+1)]
        is_prime[0] = False

        for i in range(2, n+1):
            if is_prime[i-1]:
                j = 2 * i
                while j <= n:
                    is_prime[j-1] = False
                    j += i
        return is_prime
    prime = sieve(M)
    alike = [0]
    for i in range(1,M+1,2):
        if (prime[i-1] and prime[(i+1)//2-1]):
            alike.append(alike[-1]+1)
        else:
            alike.append(alike[-1])
            
    for i in range(N):
        l,r = map(int,input().split())
        l = (l+1)//2
        r = (r+1)//2
        print(alike[r]-alike[l-1])
    
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    s = list(input())
    s.append("T")
    x,y = map(int,input().split())
    x_list = []
    y_list = []
    count = 0
    n = 0
    for i in range(len(s)+1):
        if s[i] == "F":
            count += 1
        else:
            if n == 0:
                x_list.append(count)
                n = 1
            else:
                y_list.append(count)
                n = 0
            count = 0
    x_def = {0}
    for i in x_list:
        x__def = set()
        for j in x_def:
            x__def.add(j+i)
            x__def.add(j-i)
        x_def = x__def
    if x not in x_def:
        print("No")
        exit()

    y_def = {0}
    for i in y_list:
        y__def = set()
        for j in y_def:
            y__def.add(j+i)
            y__def.add(j-i)
        y_def = y__def
    if y not in y_def:
        print("No")
        exit()
    print("Yes")

if __name__ == "__main__":
    main()

Fixed submission:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = input().split("T")
    x,y = map(int,input().split())
    l = len(s)
    dx,dy = [len(s[0])],[0]
    nx,ny = [],[]
    for i in range(1,l):
        d = len(s[i])
        if i%2 == 0:
            nx = []
            for num in dx:
                nx.append(num+d)
                nx.append(num-d)
            dx = list(set(nx))
        else:
            ny = []
            for num in dy:
                ny.append(num+d)
                ny.append(num-d)
            dy = list(set(ny))

    if (x in dx and y in dy):
        print("Yes")
    else:
        print("No")
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    edge = np.array([list(map(int,input().split())) for _ in range(N)])
    use = np.array([[True for _ in range(N)] for _ in range(N)])
    count = 0
    for k in range(N):
        for i in range(N):
            if k == i:
                continue
            for j in range(N):
                if (k == j or i == j):
                    continue
                if edge[i][j] == edge[i][k] + edge[k][j]:
                    use[i][j] = False
                elif edge[i][j] > edge[i][k] + edge[k][j]:
                    print(-1)
                    exit()
    
    ans = 0
    for i in range(N):
        ans += sum(edge[i,i:]*use[i,i:])
        
    print(ans)
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        edge[i][i] = 10**10
        
    ans = 0
    for i in range(N):
        for j in range(i):
            d = min(a+b for a,b in zip(edge[i],edge[j]))
            if edge[i][j] > d:
                print(-1)
                exit()
            elif edge[i][j] < d:
                ans += edge[i][j]

    print(ans)    

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline


def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    use = [[True for _ in range(N)] for _ in range(N)]
    count = 0
    for k in range(N):
        for i in range(N):
            if k == i:
                continue
            for j in range(N):
                if (k == j or i == j):
                    continue
                if edge[i][j] == edge[i][k] + edge[k][j]:
                    use[i][j] = False
                elif edge[i][j] > edge[i][k] + edge[k][j]:
                    print(-1)
                    exit()
    
    ans = 0
    for i in range(N):
        for j in range(i,N):
            ans += (edge[i][j]*use[i][j])
    print(ans)
    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        edge[i][i] = 10**10
        
    ans = 0
    for i in range(N):
        for j in range(i):
            d = min(a+b for a,b in zip(edge[i],edge[j]))
            if edge[i][j] > d:
                print(-1)
                exit()
            elif edge[i][j] < d:
                ans += edge[i][j]

    print(ans)    

if __name__ == "__main__":
    main()