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

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for _ in range(3**n):
        count = 0
        state = _
        x = 0
        y = 0
        for i in range(n):
            if state%3 == 1:
                count += 1
                x += 1<<i
            elif state%3 == 2:
                count += 1
                y += 1<<i
            state //= 3
        z = x|y
        
        cost = 0
        for i in range(n):
            if not (z>>i & 1):
                cost += min(xcal[x][i],ycal[y][i])
            if cost >= ans[count]:
                break
        ans[count] = min(ans[count],cost)

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,Y = map(int,input().split())
exist_flag = False
for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if not i+j+k == N:
                continue
            if Y == 10000*i + 5000*j + 1000*k:
                exist_flag = True
                break
        if exist_flag:
            break
    if exist_flag:
        break
if not exist_flag:
    i,j,k = -1, -1, -1
print(i, j, k)

### FIXED CODE ###

N,Y = map(int,input().split())
exist_flag = False
for i in range(N+1):
    for j in range(N+1-i):
        if Y == 10000*i + 5000*j + 1000*(N-i-j):
            exist_flag = True
            break
    if exist_flag:
        break
if not exist_flag:
    print(-1, -1, -1)
else:
    print(i, j, N-i-j)
### BUGGY CODE ###

def getFumidai(arr, idx):
  if idx == 0:
    return 0

  my_height = arr[idx]
  target = arr[0:idx]
  max_height = max(target)

  if (my_height >= max_height):
    return 0

  return max_height - my_height

n = int(input())
a = [int(i) for i in input().split(' ')]

result = 0

for i in range(n):
  result += getFumidai(a, i)

print(result)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
result = 0
max_height = 0

for i in range(n):
  an = a[i]
  if i == 0:
    max_height = an
    max_height_idx = 0
    continue

  if an >= max_height:
    max_height = an
    max_height_idx = i
    continue

  result += (max_height - an)

print(result)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
  a = input()
  if " " in a:
    l = list(a.split())
    if l[1] == "1":
      s = l[2] + s
    else:
      s = s + l[2]
  else:
    s = ''.join(list(reversed(s)))
print(s)

### FIXED CODE ###

s = input()
q = int(input())
s1 = ""
s2 = ""
c = 1
for i in range(q):
  a = input()
  if " " in a:
    l = list(a.split())
    c2 = 3-2*int(l[1])
    if c*c2 == 1:
      s1 = s1 + l[2]
    else:
      s2 = s2 + l[2]
  else:
    c = -c
s = s1[::-1] + s + s2
if c == 1:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
max_da=max(da)  
dp = [float("inf") for i in range(H*10000)]
dp[0]=0

for j in range(N):
    for i in range(H*10000):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H*10000):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

### FIXED CODE ###

H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))
### BUGGY CODE ###

L,R = list(map(int, input().split()))


MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

for i in range(2019):
    idx = myidx(i,i)
    MOD[idx] = 2019

MMM = []
Lmod = L % 2019
Rmod = R % 2019

if L+2019 <= R:
    MMM = MOD
elif Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

elif Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(i+1, 2019)):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

MMM.sort()
print(MMM.pop(0))


### FIXED CODE ###

L,R = list(map(int, input().split()))

MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(i+1,2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

#for i in range(2019):
#    idx = myidx(i,i)
#    MOD[idx] = 2019

MMM = []
MIN = 2019
Lmod = L % 2019
Rmod = R % 2019

if L+2019 <= R:
    for i in range(2019):
        for j in range(i+1,2019):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])
elif Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

elif Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(max(Lmod,i+1), 2019)):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

#MMM=list(set(MMM))
#MMM.sort()
#print(MMM.pop(0))
print(MIN)
### BUGGY CODE ###

k,s=map(int,input().split())
count=0

nums=[i for i in range(k+1)]

for i in range(len(nums)):
  for j in range(len(nums)):
    l = s-i-j
    if 0 <= l <=k:
      if i+j+l==s:
        count+=1
print((count))


### FIXED CODE ###

k,s=map(int,input().split())
count=0

nums=[i for i in range(k+1)]

for i in range(len(nums)):
  for j in range(len(nums)):
    if 0 <= s-i-j <= k:
      count+=1
print(count)
### BUGGY CODE ###


import sys  
import numpy as np
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
 
a_ = list(set(a))
temp = []
for i in a_:
    temp.append(a.count(i+1) + a.count(i) + a.count(i-1))
 
print(max(temp))

### FIXED CODE ###


import sys  
import numpy as np
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
k = [0] * max(3,(max(a)+1))

for p in a:
    k[p] += 1
ans = 0
for q,r,s in zip(k, k[1:] , k[2:]):
    ans = max(ans, q+r+s)

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

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

yz=[]
for i in range(Y):
    yz=yz+[ y[i]+z[j] for j in range(Z)]

yz.sort(reverse=True)

if len(yz)>3000:
    yz=yz[:3000]


n=len(yz)
ans=[]

for i in range(X):
    tmp=[yz[j]+x[i] for j in range(len(yz))]
    ans =ans+tmp

ans.sort(reverse=True)


for i in range(K):
    print(ans[i])

### FIXED CODE ###

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

ans=[]
for i in range(min(X,K)):
    tmp1=math.ceil(K/(i+1))
    for j in range(min(Y,tmp1)):
        tmp2=math.ceil(tmp1/(j+1))
        for k in range(min(Z,tmp2)):
            ans.append(x[i]+y[j]+z[k])

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    visited = set([start])
    lengths = {start: 0}
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        vf = False
        if vertex in visited:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            visited.add(vertex)
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

### FIXED CODE ###

from collections import deque

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)
### BUGGY CODE ###

ans_list = []
def make_pieces(w, d, s):
    while True:
        if w > s:
            return [s, d], [w - s, d]
        s -= w
        if d > s:
            return [w, s], [w, d - s]
        s -= d
        if w > s:
            return [w - s, d], [s, d]
        s -= w
        if d > s:
            return [w, s], [w, d - s]
        s -= d


while True:
    n, w, d = map(int, input().split())
    P = [[w, d]]
    if n == 0 and w == 0 and d == 0:
        break
    for i in range(n):
        p, s = map(int, input().split())
        new_pieces = make_pieces(P[p - 1][0], P[p - 1][1], s)
        #print(new_pieces)
        if new_pieces[0][0] * new_pieces[0][1] < new_pieces[1][0] * new_pieces[1][1]:
            P = P[:p - 1] + [new_pieces[0]] + [new_pieces[1]] + P[p:]
        else:
            P = P[:p - 1] + [new_pieces[1]] + [new_pieces[0]] + P[p:]
        #print(P)

    S_list = []
    for i in P:
        S_list.append(i[0] * i[1])

    S_list.sort()
    ans_list.append(S_list)
    
for i in range(len(ans_list)):
    I = ans_list[i]
    for j in range(len(I)):
        J = I[j]
        if i == len(ans_list) - 1 and j == len(I) - 1:
            print(J, end = "")
        else:
            print(J, end = " ")
    print()


### FIXED CODE ###

ans_list = []
def make_pieces(w, d, s):
    if w == 0 and d == 0:
        print(w, d, s)
    s %= (2 * w + 2 * d)
    while True:
        if w > s:
            return [s, d], [w - s, d]
        s -= w
        if d > s:
            return [w, s], [w, d - s]
        s -= d
        if w > s:
            return [w - s, d], [s, d]
        s -= w
        if d > s:
            return [w, s], [w, d - s]
        s -= d


while True:
    n, w, d = map(int, input().split())
    P = [[w, d]]
    if n == 0 and w == 0 and d == 0:
        break
    for i in range(n):
        p, s = map(int, input().split())
        new_pieces = make_pieces(P[p - 1][0], P[p - 1][1], s)
        #print(new_pieces)
        if new_pieces[0][0] * new_pieces[0][1] < new_pieces[1][0] * new_pieces[1][1]:
            P = P[:p - 1] + P[p:] + [new_pieces[0]] + [new_pieces[1]]
        else:
            P = P[:p - 1] + P[p:] + [new_pieces[1]] + [new_pieces[0]]
        #print(P)

    S_list = []
    for i in P:
        S_list.append(i[0] * i[1])

    S_list.sort()
    ans_list.append(S_list)

for i in range(len(ans_list)):
    I = ans_list[i]
    for j in range(len(I)):
        J = I[j]
        if j == len(I) - 1:
            print(J, end = "")
        else:
            print(J, end=" ")
    print()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    l1 = l2 = l3 = 0
    l = [int(i) for i in input().split()]
    for i in l:
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1
    a = l2+l3
    dp = [[[0]*(l3+1) for i in range(a+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,a)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n/(s+t+k)
                if s > 0:
                    count += dp[s-1][t][k]*(s/(s+t+k))     
                if t > 0 :
                    count += dp[s+1][t-1][k]*(t/(s+t+k))
                if k > 0 :
                    count += dp[s][t+1][k-1]*(k/(s+t+k))

                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()



### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

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

k = int(m/n)
ans = 1
for i in range(k):
    if m % (k-i) == 0:
        ans = k-i
        break
print(ans)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd (a, b)


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = reduce(lcm, A, 1)
ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

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


def lcm(a, b):
    return a * b // gcd (a, b)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

l %= MOD
ans = 0
for a in A:
  ans += (l * power(a, MOD-2)) % MOD
  ans %= MOD

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

if __name__ == '__main__':
    N = int(input())
    X = list(map(int, input().split()))
    x = sorted(X[:])
    for i in range(N):
        _x = x[:]
        _x.remove(X[i])
        print(_x[int(N/2-1)])


### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    X = list(map(int, input().split()))
    x = sorted(X[:])
    min_median = x[int(N/2-1)]
    max_median = x[int(N/2)]
    for i in range(N):
        if X[i] <= min_median:
            print(max_median)
        else:
            print(min_median)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
tmp2 = 0
for i in range(N):
  if(i == 0):
    tmp=A.count(1)
    print(str(tmp))
  else:
    tmp2 = i + 1
    tmp=A.count(tmp2)
    print(str(tmp))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
for i in range(1,N+1):
  print(c[i])
### BUGGY CODE ###

from numba import jit

n=int(input())
s=input()
R=[]
G=[]
B=[]

@jit
def f():
  for i in range(n):
    if s[i]=="R":
      R.append(i)
    elif s[i]=="G":
      G.append(i)
    else:
      B.append(i)
  r=len(R)
  g=len(G)
  b=len(B)
  if r==0 or g==0 or b==0:
    return 0
  else:
    ans=r*g*b
    m=0
    for j in range(1,n-1):
      for k in range(1,min(j,n-1-j)+1):
        lt=s[j-k]
        md=s[j]
        rt=s[j+k]
        if lt!=md and md!=rt and rt!=lt:
          m+=1
    return ans-m
print(f())

### FIXED CODE ###

n=int(input())
s=input()
R=[]
G=[]
B=[]
def f():
  for i in range(n):
    if s[i]=="R":
      R.append(i)
    elif s[i]=="G":
      G.append(i)
    else:
      B.append(i)
  r=len(R)
  g=len(G)
  b=len(B)
  if r==0 or g==0 or b==0:
    return 0
  else:
    ans=r*g*b
    m=0
    for j in range(1,n-1):
      for k in range(1,min(j,n-1-j)+1):
        lt=s[j-k]
        md=s[j]
        rt=s[j+k]
        if lt!=md and md!=rt and rt!=lt:
          m+=1
    return ans-m
print(f())
### BUGGY CODE ###

import math
K = int(input())
result = 0
sum = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        result = math.gcd(a, b)
        for c in range(1,K+1):
            result = math.gcd(a, b)
            sum += math.gcd(result, c)

print(sum)        

### FIXED CODE ###

K = int(input())
import math
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        value = math.gcd(i,j)
        for k in range(1, K+1):
            sum += math.gcd(value,k)
 
print(sum)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
A = np.empty((0, 2), int)
for i in range(n):
  A = np.append(A, np.array([[i+1, a[i]]]), axis = 0)

ans = str(A[A[:, 1].argsort(), :][:, 0]).replace('[', '').replace(']', '')
print(ans)

      



### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
A = np.zeros(n)
for i in range(n):
  A[a[i] - 1] = i

print(str([int(A[i]) + 1 for i in range(n)]).replace('[', '').replace(']', '').replace(',', ''))
### BUGGY CODE ###

n = int(input())
a,b,c=[],[],[]
for i in range(n):
    a_b = list(map(int, input().split()))
    a.append(a_b[0])
    b.append(a_b[1])
    c.append(a_b[0]+a_b[1])
taka,aoki=0,0

for i in range(n):
    num = c.index(max(c))
    if i % 2 ==0:
        taka = taka + a[num]
    else:
        aoki = aoki + b[num]
    del a[num]
    del b[num]
    del c[num]
print(taka-aoki)


### FIXED CODE ###

n = int(input())
a,b,c=[],[],[]
for i in range(n):
    a_b = list(map(int, input().split()))
    a.append(a_b[0])
    b.append(a_b[1])
    c.append(a_b[0]+a_b[1])
d = sorted(enumerate(c), key=lambda x: x[1], reverse=True)
taka,aoki=0,0
for i in range(n):
    if i % 2 ==0:
        taka = taka + a[d[i][0]]
    else:
        aoki = aoki + b[d[i][0]]
print(taka-aoki)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
ans=-float("inf")
for i in range(a,b+1):
    for j in range(c,d+1):
        ans=max(ans,i*j)
print(ans)


### FIXED CODE ###

a,b,c,d=map(int,input().split())
print(max(a*c,a*d,b*c,b*d))
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

h, w, d = map(int, input().split())
a = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    ai = list(map(int, input().split()))
    for j in range(w):
        a[ai[j]] = [i+1, j+1]

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

MAX_LOG = math.ceil(math.log2(h*w))
# MAX_LOG = 18
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, (r-l)//d))


### FIXED CODE ###

import math
h, w, d = map(int, input().split())
a = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    ai = list(map(int, input().split()))
    for j in range(w):
        a[ai[j]] = [i+1, j+1]

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

# MAX_LOG = math.ceil(math.log2(h*w))
MAX_LOG = 18
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, (r-l)//d))
### BUGGY CODE ###

import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A))
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if B[i][j] == B[i][k] + B[k][j]:
                    A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()