Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        y *= i
    return x*pow(y, mod-2, mod)%mod

ans = (2**n+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)
### BUGGY CODE ###

n = int(input())
al = list(map(int, input().split()))
q = int(input())
bl = []
cl = []
for i in range(q):
    b,c = map(int, input().split())
    bl.append(b)
    cl.append(c)

shoki = sum(al)
for i in range(q):
    b = bl[i]
    c = cl[i]
    for i,youso in enumerate(al):
        if youso == b:
            ali = al[i]
            al[i] = c
            shoki += c - ali
    print(shoki)


### FIXED CODE ###

n = int(input())
al = list(map(int, input().split()))
q = int(input())
bl = []
cl = []
for i in range(q):
    b,c = map(int, input().split())
    bl.append(b)
    cl.append(c)

shoki = sum(al)

dic = {}
for i in al:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1


for i in range(q):
    b = bl[i]
    c = cl[i]
    if b in dic:
        bcount = dic.pop(b)
    else:
        bcount = 0
    if c in dic:
        dic[c] += bcount
    else:
        dic[c] = bcount
    shoki += (c - b)*bcount
    print(shoki)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))

a.append(0)

for i in range(n):
    cost=0
    pv=0
    nx=0
    for j in range(len(a)):
        if i == j:
            continue
        pv, nx = nx, a[j]
        cost+=abs(pv-nx)

    print(cost)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))

a=[0]+a+[0]

cost=[abs(a[i]-a[i+1]) for i in range(len(a)-1)]
total=sum(cost)

ans=0
for i in range(n):
    ans = total - cost[i] - cost[i+1] + abs(a[i+2]-a[i])
    print(ans)
### BUGGY CODE ###

import math

n, m = map(int, input().split())
A = list(map(int, input().split()))
a = sorted(A, reverse = True)
cnt = 0
ans = 0
while cnt < m:
    max_a = max(a)
    for i in range(n):
        if cnt == m:
            break
        if a[i] == max_a:
            cnt += 1
            a[i] = a[i]/2
for j in a:
    ans += math.floor(j)

print(ans)

### FIXED CODE ###

import heapq, math

n, m = map(int, input().split())
A = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), A))
heapq.heapify(a)
for i in range(m):
    max_a = heapq.heappop(a)
    heapq.heappush(a, math.ceil(max_a/2))
print(-sum(a))
### BUGGY CODE ###

import copy

N,C=map(int,input().split())
channel=[tuple(map(int,input().split())) for i in range(N)]
channel=sorted(channel,key=lambda cha: cha[0])

n=0
while(channel!=[]):
    c=copy.copy(channel)
    n+=1
    pro=channel[0]
    c.remove(pro)
    for i in channel:
        if i[0]>pro[1]:
            pro=i
            c.remove(pro)
    channel=c
print(n)


### FIXED CODE ###

N,C=map(int,input().split())
channel=[tuple(map(int,input().split())) for i in range(N)]
channel=sorted(channel,key=lambda cha: cha[0])

n=0
while(channel!=[]):
    c=[]
    n+=1
    pro=channel[0]
    channel.remove(pro)
    for i in channel:
        if i[0]>pro[1]:
            pro=i
        elif(i[0]==pro[1] and i[2]==pro[2]):
            pro=i
        else:
            c.append(i)
    channel=c
print(n)
### BUGGY CODE ###

n=int(input())
Alist=[int(i) for i in input().split(" ")]
Blist=[int(i) for i in input().split(" ")]
sumA=sum(Alist)
sumB=sum(Blist)
Dlist=[]
muinus=0
muinus_num=0
count=0
if sumA<sumB:
    print(-1)
else:
    for i in range(n):
        AB=Alist[i]-Blist[i]
        Dlist.append(AB)
        if AB<0:
            muinus+=AB
            muinus_num+=1
    while muinus<0:
        muinus+=max(Dlist)
        Dlist.remove(max(Dlist))
        count+=1
    print(muinus_num+count)

### FIXED CODE ###

n=int(input())
Alist=[int(i) for i in input().split(" ")]
Blist=[int(i) for i in input().split(" ")]
sumA=sum(Alist)
sumB=sum(Blist)
Dlist=[]
muinus=0
muinus_num=0
count=0
if sumA<sumB:
    print(-1)
else:
    for i in range(n):
        AB=Alist[i]-Blist[i]
        Dlist.append(AB)
        if AB<0:
            muinus+=AB
            muinus_num+=1
    Dlist.sort(reverse=True)
    while muinus<0:
        muinus+=Dlist[count]
        count+=1
    print(muinus_num+count)
### BUGGY CODE ###

def search(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            elif dp[x-1][y] > dp[x][y-1]:
                dp[x][y] = dp[x-1][y]
            else:
                dp[x][y] = dp[x][y-1]
    return dp[-1][-1]

N = int(input())
for i in range(N):
    X = input()
    Y = input()
    print(search(X, Y))


### FIXED CODE ###

def ser(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for i, x in enumerate(X, 1):
        tmp = dp[i]
        pre = dp[i-1]
        for j, y in enumerate(Y, 1):
            if x == y:
                tmp[j] = pre[j-1] + 1
            elif pre[j] < tmp[j-1]:
                tmp[j] = tmp[j-1]
            else:
                tmp[j] = pre[j]
    return(dp[-1][-1])

for _ in range(int(input())):
    X, Y = input(), input()
    print(ser(X, Y))
### BUGGY CODE ###

s = input()
ans = 0
while "0" in s and "1" in s:
  ans += s.count("10")
  s = s.replace("10", "")
  ans += s.count("01")
  s = s.replace("01", "")
print(ans*2)


### FIXED CODE ###

s=input();print(min(s.count("0"),s.count("1"))*2)
### BUGGY CODE ###

s = '0' + input()
n = len(s)
cnt = 0

dp = []

for i in range(1, n-2):
	for j in range(i+3, n+1):
		tmp = int(s[i:j])
		if tmp in dp:
			cnt += 1
		elif tmp % 2019 == 0:
			dp.append(tmp)
			cnt += 1

print(cnt)

### FIXED CODE ###

s = input()
n = len(s)

MOD = 2019
T = [1] + [0] * 2018
d, p = 0, 1
for c in reversed(s):
	d = (d + p * int(c)) % MOD
	p = p * 10 % 2019
	T[d] += 1

print(sum(x * (x - 1) // 2 for x in T))
### BUGGY CODE ###



def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def solve():
  N = int(input())
  A = [int(i) for i in input().split(' ')]
  divisors_list = {}
  for i in A:
    divisors_list[i] = []

  for k,i in enumerate(A):
    for j in make_divisors(i):
      try:
        divisors_list[j].append(k)
      except:
        continue

  pass_li = {}
  for i in range(N):
    pass_li[i] = 1

  for i in range(N):
    tmp = pass_li[i]
    for j in divisors_list[A[i]]:
      pass_li[j] = 0
    pass_li[i] = tmp 


  print(sum(pass_li.values()))

 
if __name__ == '__main__':
    solve()


  
  


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1

c = 0
for i in A:
  if dp[i] == 1:
    c += 1

print(c)
### BUGGY CODE ###

n = int(input())
s = input()
code = [[-1,-1,-1] for i in range(1000)]

for i in range(n):
    si = int(s[i])
    for j in range(100):
        if code[j*10+si][1] < i and code[j*10+si][1] > -1 and code[j*10+si][2] == -1:
            code[j*10+si][2] = i
            #print(i,j*10+si,2)
        if code[si*100+j][0] == -1:
            code[si*100+j][0] = i
            #print(i,si*100+j,0)
        if code[(j//10)*100+si*10+j%10][0] < i and code[(j//10)*100+si*10+j%10][0] > -1 and code[(j//10)*100+si*10+j%10][1] == -1:
            code[(j//10)*100+si*10+j%10][1] = i
            #print(i,(j//10)*100+si*10+j%10,1)

ans = 0
for i in range(1000):
    if code[i][2] > -1:
        ans += 1

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/sumitrust2019/submissions/13016562を見た

n = int(input())
s = input()
ans = 0

pin = [str(i).zfill(3) for i in range(1000)]

for i in pin:
    idx = -1
    for j in i:
        idx = s.find(j,idx+1)
        if idx < 0:
            break
    else:
        ans += 1

print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input().rstrip()
    T = input().rstrip()
    s = len(S)
    t = len(T)

    dp = [[0]*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j])

    #復元
    res = ''
    while s != 0 and t != 0:
        if dp[s][t] == dp[s-1][t]:
            s -= 1
        elif dp[s][t] == dp[s][t-1]:
            t -= 1
        else:
            s -= 1
            t -= 1
            res = S[s] + res
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input().rstrip()
    T = input().rstrip()
    s = len(S)
    t = len(T)

    dp = [[0]*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j])

    #復元
    res = ''
    while s != 0 and t != 0:
        if dp[s][t] == dp[s-1][t]:
            s -= 1
        elif dp[s][t] == dp[s][t-1]:
            t -= 1
        else:
            s -= 1
            t -= 1
            res = S[s] + res
    print(res)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

a = []
i = 1
while True:
  if A[0] % i == 0:
    a += [i, A[0]//i]
  i += 1
  if i**2 > A[0]:
    break
    
b = []
i = 1
while True:
  if A[1] % i == 0:
    a += [i, A[1]//i]
  i += 1
  if i**2 > A[1]:
    break
#print(a, b)
ans = 1
for i in a:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
for i in b:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
      
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

a = []
i = 1
while True:
  if A[0] % i == 0:
    a += [i, A[0]//i]
  i += 1
  if i**2 > A[0]:
    break
    
b = []
i = 1
while True:
  if A[1] % i == 0:
    a += [i, A[1]//i]
  i += 1
  if i**2 > A[1]:
    break
#print(a, b)
ans = 1
for i in a:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
for i in b:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
      
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n, m = map(int, input().split())
S = input()
T = input()

gcd = gcd(n, m)
L = int(n * m / gcd)

a = int(L/n)
b = int(L/m)

flag=True

for i in range(L):
    if (int(i%a) == 0 and int(i%b) == 0):
        if not S[int(i/a)] == T[int(i/b)]:
            flag = False
if flag:
    print(L)
else:
    print("-1")


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n, m = map(int, input().split())
S = input()
T = input()

gcd = gcd(n, m)
L = int(n * m / gcd)

a = int(L/n)
b = int(L/m)

flag=True

if n > m:
    for j in range(n):
        i = j * a
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
else:
    for j in range(m):
        i = j * b
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
                
if flag:
    print(L)
else:
    print("-1")
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())

s = [] * 2
print(0, flush=True)
s[0] = input()
if s[0] == 'Vacant':
    exit()

l, r = 0, N
while r - l > 2:
    m = (l + r) // 2
    print(m, flush=True)
    s[1] = input()
    if s[1] != 'Vacant':
        exit()

    if s[0] == s[1]:
        l, r = (l, m) if (m - l) % 2 == 1 else (m, r)
    else:
        l, r = (m, r) if (m - l) % 2 == 1 else (l, m)
    s[0] = s[1]
print((l + r) // 2, flush=True)
exit()


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[-inf]
for _ in range(A):
    s.append(int(input()))
s.append(inf)

t=[-inf]
for _ in range(B):
    t.append(int(input()))
t.append(inf)
from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))




### FIXED CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[-inf]
for _ in range(A):
    s.append(int(input()))
s.append(inf)

t=[-inf]
for _ in range(B):
    t.append(int(input()))
t.append(inf)
from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))
### BUGGY CODE ###

def func2(l, value):
    i = -1
    c = len(l)
    result = []
    while i < c:
        try:
            i = l.index(value, i + 1)
            result.append(i)
        except:
            return result
    return result

T=list(input())
que_list=(func2(T,"?"))
T_now= T
ans_T = ''.join(T)
count = 0 
N=T.count("?")
op = ["P"] * N

for i in range(2 ** N):
    op_now = op
    for j in range(N):
        if ((i >> j) & 1):
            op_now[N - 1 - j] = "D"
    for k,que_index in zip(op_now,que_list):
        T[que_index]=k
    test_T=''.join(T)
    check_value=test_T.count("D")+test_T.count("DP")
    if(count < check_value):
        ans_T = test_T
        count = check_value
    T=T_now
print(''.join(ans_T))

### FIXED CODE ###

def func2(l, value):
    i = -1
    c = len(l)
    result = []
    while i < c:
        try:
            i = l.index(value, i + 1)
            result.append(i)
        except:
            return result
    return result

T=list(input())
que_list=(func2(T,"?"))
for i in que_list:
    T[i]='D'
print(''.join(T))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 1
for i in range(N):
    ans *= A[i]

if ans <= 1e18: print(ans)
else: print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 1
flg = True

if 0 in A: print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 1e18:
            flg = False
            break

    if flg: print(ans)
    else:print(-1)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+i
            y0 = y+j
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
### BUGGY CODE ###

import numpy as np
from numba import njit

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

expv[0][0][0] = 0.0

def get_expv(i, j, k):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3]))



### FIXED CODE ###

import numpy as np
from numba import njit


@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

# for a in A:
#     print(a)
# 余分な辺を消去する問題
graph = floyd_warshall(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))


### FIXED CODE ###

import copy

def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    global N
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
graph = copy.deepcopy(A)
# for a in A:
#     print(a)
# 余分な辺を消去する問題
A = warshal_floyd(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))
### BUGGY CODE ###


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
R=[[0 for i in range(w)]for i in range(h)]
D=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            if j==0:
                R[i][j]=1
            else:
                R[i][j]=R[i][j-1]+1

        if s[h-i-1][w-j-1]=='.':
            if j==0:
                L[h-i-1][w-j-1]=1
            else:
                L[h-i-1][w-j-1]=L[h-i-1][w-j]+1


        if s[h-i-1][w-j-1]=='.':
            if i==0:
                U[h-i-1][w-j-1]=1
            else:
                U[h-i-1][w-j-1]=U[h-i][w-j-1]+1

        if s[i][j]=='.':
            if i==0:
                D[i][j]=1
            else:
                D[i][j]=D[i-1][j]+1


for i in range(h):
    for j in range(w):
        ans=max(ans,L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)

print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
R=[[0 for i in range(w)]for i in range(h)]
D=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            if j==0:
                R[i][j]=1
            else:
                R[i][j]=R[i][j-1]+1

        if s[h-i-1][w-j-1]=='.':
            if j==0:
                L[h-i-1][w-j-1]=1
            else:
                L[h-i-1][w-j-1]=L[h-i-1][w-j]+1


        if s[h-i-1][w-j-1]=='.':
            if i==0:
                U[h-i-1][w-j-1]=1
            else:
                U[h-i-1][w-j-1]=U[h-i][w-j-1]+1

        if s[i][j]=='.':
            if i==0:
                D[i][j]=1
            else:
                D[i][j]=D[i-1][j]+1


for i in range(h):
    for j in range(w):
        ans=max(ans,L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)

print(ans)