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

# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            else:
                dp[j] = max(dp_prev[j], dp[j - 1])

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs_sol(x, y))



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

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

import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

s = ns()[::-1]
ans = "YES"

while len(s) > 1:
    if s[:5] == "maerd":
        s = s[5:]
    elif s[:7] == "remaerd":
        s = s[7:]
    elif s[:5] == "esare":
        s = s[5:]
    elif s[:6] == "resare":
        s = s[6:]
    else:
        ans = "NO"

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

s = ns()[::-1]
ans = "YES"

while len(s) > 1:
    if s[:5] == "maerd":
        s = s[5:]
    elif s[:7] == "remaerd":
        s = s[7:]
    elif s[:5] == "esare":
        s = s[5:]
    elif s[:6] == "resare":
        s = s[6:]
    else:
        ans = "NO"
        s = ""

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

import math

N = int(input())
An = [int(x) for x in input().split()]  
Cn = [An.count(i) for i in range(1,N+1)]  # どの数字が何個あるか？

# ボールを全部使えるときの合計を求める
s = 0
for i in range(N):
    if Cn[i] > 1:
        s += int(math.factorial(Cn[i]) / (math.factorial(Cn[i]-2) * 2))
        # s += int(fact(Cn[i]) / (fact(Cn[i]-2) * 2))

for k in range(N):
    print(s - (Cn[An[k]-1]-1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
### BUGGY CODE ###

N=int(input())
count=0
a=list(map(int,input().split()))
maxi=max(a)
mini=min(a)
for i in range(N-mini):
  for j in range(i+a[i]+1,min(N,i+a[i]+1+maxi)):
    if j-i==a[i]+a[j]:
      count+=1
print(count)

### FIXED CODE ###

N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*N
maxi=max(a)
for i in range(N):
  s.append(1+i-a[i])
  if 1+i+a[i]<N:
    num[1+i+a[i]]+=1
for i in range(N):
  if s[i]>=0:
    count+=num[s[i]]
print(count)
### BUGGY CODE ###


s = input()

q = int(input())


for i in range(q):
    li = input().split()
    if li[0] == "2":
        if li[1] =="1":
            s = li[2] + s

        else:
            s = s + li[2]

    else:
        s = s[::-1]

print(s)


### FIXED CODE ###


s = input()

q = int(input())
x = []
y = []

flag = 0

for i in range(q):
    li = list(input().split())
    if flag%2 == 0:
        if li[0] == "2":
            if li[1] =="1":
                x.append(li[2])
            else:
                y.append(li[2])
        else:
            flag += 1

    else:
        if li[0] == "2":
            if li[1] =="1":
                y.append(li[2])
            else:
                x.append(li[2])
        else:
            flag += 1

if flag%2 == 0:
    x = x[::-1]
    print("".join(x)+s+"".join(y))

else:
    s = s[::-1]
    y = y[::-1]
    print("".join(y)+s+"".join(x))
### BUGGY CODE ###

import math
from functools import reduce
k = int(input())

def gcd (*numbers):
    return reduce(math.gcd, numbers)
    def  gcd_list (numbers):
        return reduce(math.gcd, numbers)
ans = 0

for i in range(k):
    for j in range(k):
        for l in range(k):
            ans += gcd(i + 1, j + 1, l + 1)

print(ans)


### FIXED CODE ###

import math
k = int(input())
ans = 0

for a in range(k):
    for b in range(k):
        d = math.gcd(a + 1, b + 1)
        for c in range(k):
            ans += math.gcd(d, c + 1)

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

N=int(input())
l=list(map(int,input().split()))
v=1
for i in range(N):
    v*=l[i]
if v>10**18:
    print('-1')
else:
    print(v)


### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
v=1
if l.count(0)!=0:
    print('0')
else:
    for i in range(N):
        v*=l[i]
        if v>10**18:
            print('-1')
            exit()
    print(v)
### BUGGY CODE ###

def divisor(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
  

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

for i,num in enumerate(A):
    for div in divisor(num):
        FLG = True
        if div in A[:i] + A[i+1:]:
            FLG = False
            break
    if FLG:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (A[-1]+1)

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    for j in range(2*num, A[-1]+1, num):
        dp[j] = False

print(len([i for i in A if dp[i]]))
### BUGGY CODE ###

n = int(input())

ls = list(map(int, input().split()))
ls.sort()

rg = range(1, n + 1)

for i in rg:
    print(ls.count(i))
    if ls.count(i) != 0:
        ls.remove(i)


### FIXED CODE ###

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

ls2 =[0 for x in range(n)]
#0がn個のリストを用意する

for x in ls:
    ls2[x - 1] += 1

for x in range(n):
    print(ls2[x])
### BUGGY CODE ###

N,M = map(int,input().split())
L_list = []
R_list = []
for o in range(M):
    L,R = map(int,input().split())
    L_list.append(L)
    R_list.append(R)

count = set(range(L_list[0],R_list[0]+1))
for i in range(1,M):
    count = count & set(range(L_list[i],R_list[i]+1))

ans = len(count)
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
L_list = []
R_list = []
for o in range(M):
    L,R = map(int,input().split())
    L_list.append(L)
    R_list.append(R)
L_max = max(L_list)
R_min = min(R_list)
    
if L_max <= R_min:
    ans = R_min - L_max + 1
else:
    ans = 0
print(ans)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
x=0
d.sort()
t.sort()
for i in range(m):
  if t[i] in d:
    d.remove(t[i])
  else:
    x=1
    break
if x==0:print('YES')
else:print('NO')

### FIXED CODE ###

from collections import Counter
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
D=Counter(d);T=Counter(t)
x=0
for i in list(set(t)):
  if D[i]<T[i]:
    x=1
    break
if x==0:print('YES')
else:print('NO')
### BUGGY CODE ###

from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,m=MI()
to=[[] for _ in range(n)]
inf=10**6
for _ in range(m):
    u,v,c=MI1()
    to[u].append((v,c))
    to[v].append((u,c))
hp=[]
dd={}
heappush(hp,(0,0,-1))
dd[0,-1]=0
while hp:
    d,u,c=heappop(hp)
    if u==n-1:
        print(d)
        break
    if d>dd[u,c]:continue
    for v,nc in to[u]:
        nd=d if c==nc else d+1
        if (v,nc) in dd and nd>=dd[v,nc]:continue
        dd[v,nc]=nd
        heappush(hp,(nd,v,nc))
else:
    print(-1)


### FIXED CODE ###

import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from collections import deque

def solve():
    dist = [inf] * len(to)
    q = deque()
    q.append((0, 0))
    dist[0] = 0
    while q:
        d, i = q.popleft()
        if d > dist[i]: continue
        if i < n:
            for j in to[i]:
                if dist[j] <= d + 1: continue
                dist[j] = d + 1
                q.append((d + 1, j))
        else:
            for j in to[i]:
                if j == n - 1:
                    print(dist[i])
                    exit()
                if dist[j] <= d: continue
                dist[j] = d
                q.appendleft((d, j))
    print(-1)

inf=10**9
n,m=MI()
to=[]
uctoi={}

for u in range(n):
    to.append([])
    uctoi[u,0]=u

for _ in range(m):
    u,v,c=MI()
    u,v=u-1,v-1
    if (u,c) not in uctoi:
        i=uctoi[u,c]=len(to)
        to.append([])
        to[i].append(u)
        to[u].append(i)
    else:i=uctoi[u,c]
    if (v,c) not in uctoi:
        j=uctoi[v,c]=len(to)
        to.append([])
        to[j].append(v)
        to[v].append(j)
    else:j=uctoi[v,c]
    to[i].append(j)
    to[j].append(i)
#print(to)
#print(fin)

solve()
### BUGGY CODE ###

from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1

    for i in range(1,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if i in sa and i!=ai:
                ans-=1
                break
            if i>1 and ai//i in sa:
                ans-=1
                break
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
print(ans)
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
b.sort()
r = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        if b[j + 1] >= b[i] + b[j]:
            continue
        for k in range(j+1, a):
            if b[k] >= b[i] + b[j]:
                break
            r += 1
print(r)


### FIXED CODE ###

def binsearch(l, r, fn, i, j):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m, i, j):
            l = m
        else:
            r = m
    return l

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    def fn(m, i, j):
        a = L[m]
        b = L[i]
        c = L[j]
        if a < b + c and b < c + a and c < a + b:
            return True
        return False
    r = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if fn(j+1, i, j):
                r += binsearch(j+1, N, fn, i, j) - j
    return r
print(main())
### BUGGY CODE ###

from collections import deque
def solve():
  n = int(input())
  treepath = [[False]*n for _ in range(n)]
  treenode = [[]*n for _ in range(n)]
  treecolor = [-1]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treepath[u][v] = w%2
    treepath[v][u] = w%2
    treenode[u].append(v)
    treenode[v].append(u)

  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode in treenode[a]:
      if treecolor[nextnode] != -1:
        continue
      else:
        query.append((nextnode,treepath[a][nextnode],nextc))  
  #print(treecolor)
  for i in treecolor:
    print(i)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  treenode = [[] for _ in range(n)]
  treecolor = [-2]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append((v,w%2))
    treenode[v].append((u,w%2))
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode,weight in treenode[a]:
      if treecolor[nextnode] != -2:
        continue
      else:
        query.append((nextnode,weight,nextc))  
        treecolor[nextnode] = -1
  for i in treecolor:
    print(i)
solve()
### BUGGY CODE ###

from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
pr = [True]*(10**6+5)

def prime_fact(x):
    memo = [0]*(x+1)
    primes = []
    if x <= 1: return False
    for i in range(2, x+1):
        if memo[i]:
            continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]:
                continue
            memo[j] = i
    a = x
    b = []
    while a > 1:
        b.append(memo[a])
        a //= memo[a]
    return b


for a in A:
    if a == 1: continue
    for p in set(prime_fact(a)):
        if not pr[p]:
            break
        pr[p] = False
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from functools import reduce
from math import gcd 

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

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo, primes

memo, primes = furui(10**6+5)

pr = [True]*(10**6+5)
for a in A:
    if a == 1: continue
    while a != 1:
        w = memo[a]
        if not pr[w]:
            break
        pr[w] = False
        while a%w == 0:
            a = a // w
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n = int(input())
s = input()

su = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for lis in ['R','G','B']:
                if lis != s[i] and lis != s[j]:
                    try:
                        su -= s[2*j-i].count(lis)
                    except:
                        pass

print(su)

### FIXED CODE ###

n = int(input())
s = input()

su = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for lis in ['R','G','B']:
                if lis != s[i] and lis != s[j]:
                    try:
                        su -= s[2*j-i].count(lis)
                    except:
                        pass

print(su)
### BUGGY CODE ###

S = input()
numQ = int(input())
lead = 1

for i in range(numQ):
  Q = input()
  if Q[0] == "1":
    lead *= -1
  else:
    if Q[2] == "1":
      if lead == 1:
        S = Q[4] + S
      else:
        S = S + Q[4]
    else:
      if lead == 1:
        S = S + Q[4]
      else:
        S = Q[4] + S
if lead == -1:
  S = S[::-1]

print(S)
      
      

### FIXED CODE ###

S = input()
numQ = int(input())
lead = 1
front = ""
rear = ""
for i in range(numQ):
  Q = input()
  if Q[0] == "1":
    lead *= -1
  else:
    if Q[2] == "1":
      if lead == 1:
        front = Q[4] + front
      else:
        rear = rear + Q[4]
    else:
      if lead == 1:
        rear = rear + Q[4]
      else:
        front = Q[4] + front
S = front + S + rear
if lead == -1:
  S = S[::-1]

print(S)
### BUGGY CODE ###

K = int(input())

if K%10==0 or K%10==2 or K%10==4 or K%10==5 or K%10==6 or K%10==8:
    print(-1)
else:
    num = 0
    i = 0
    while True:
        num += 7 * 10**i
        if num%K == 0:
            break
        i += 1
    print(i+1)


### FIXED CODE ###

K = int(input())

if K % 7 == 0:
    L = 9 * K / 7
else:
    L = 9 * K

if L % 2 == 0 or L % 5 == 0:
    print(-1)
else:
    rest = 1
    ans = 0
    while True:
        rest *= 10
        ans += 1
        rest = rest % L
        if rest == 1:
            break
    print(ans)
### BUGGY CODE ###

N=int(input())
H=list(map(int, input().split()))
Max=0
count=0
for i in range(N):
  count=0
  for j in range(N - i - 1):
    if H[i + j] >= H[i + j + 1]:
      count+=1
    else:
      count=0
    if Max < count:
      Max = count
print(Max)

### FIXED CODE ###

N=int(input())
H=list(map(int, input().split()))
Max=0
count=0
index=0
for i in range(1,N):
  if H[index] >= H[i]:
    count+=1
    index+=1
  else:
    count=0;
    index = i
  if Max < count:
    Max = count
print(Max)
### BUGGY CODE ###

n = int(input())
seq = [x for x in input().split(' ')]

b = []

for i in range(n):
    b.append(seq[i])
    
    start = 0
    end = i

    while (start <= end):
        temp = b[end]
        b[end] = b[start]
        b[start] = temp
        start += 1
        end -= 1
    

print(' '.join(b))

### FIXED CODE ###

n = int(input())
seq = [x for x in input().split(' ')]

b = []

if n % 2 == 0:
    for j in range(n-1, -1, -2):
        b.append(seq[j])
    for i in range(0, n, 2):
        b.append(seq[i])

else:
    for j in range(n-1, -1, -2):
        b.append(seq[j])
    
    for i in range(1, n, 2):
        b.append(seq[i])

print(' '.join(b))
### BUGGY CODE ###

N = int(input())

A = list(map(int,input().split()))
i = 0
while True:
    A.sort()
    for a in range(len(A)-1):
        A[a+1] = A[a+1] - A[a]

    A = [i for i in A if  i > 0]
    if len(A) == 1:
        break

print(A[0])


### FIXED CODE ###

N = int(input())

A = list(map(int,input().split()))
i = 0
while True:
    A.sort()
    for a in range(len(A)-1):
        if not(A[a] == 0) and A[a+1] % A[a] == 0:
                A[a+1] = A[a+1] % A[a]
        else:
            A[a+1] = A[a+1] - A[a]

    A = [i for i in A if  i > 0]
    if len(A) == 1:
        break

print(A[0])
### BUGGY CODE ###

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

dp=[[0]*(s+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
ans=0

# i indicade low , c indicade column
for i,w in enumerate(a):
    for c in range(s+1):
        dp[i][c]+=dp[i-1][c]
    for c in range(s-w+1):
        dp[i][c+w]+=dp[i-1][c]
    ans+=dp[i][-1]
    ans%=998244353

print(ans)


### FIXED CODE ###

import numpy as np

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

dp=[np.zeros(s+1,dtype=np.int64) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
ans=0

for i,w in enumerate(a):
    dp[i]+=dp[i-1]
    dp[i][w:]+=dp[i-1][:-w]
    dp[i]%=998244353
    ans+=dp[i][-1]
    ans%=998244353

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

s = list(input())
k = int(input())

l = []
for i in range(len(s)):
    for y in range(i+1,len(s)+1):
        #print(''.join(s[i:y]))
        if not ''.join(s[i:y]) in l:
            l.append(''.join(s[i:y]))

l.sort()
if not l:
    print(s[0])
else:
    print(l[k-1])


### FIXED CODE ###

s = list(input())
k = int(input())

l = []
for i in range(len(s)):
    for y in range(k):
#        print(''.join(s[i:i+y+1]))
        if not ''.join(s[i:i+y+1]) in l:
            l.append(''.join(s[i:i+y+1]))

l.sort()
if not l:
    print(s[0])
else:
    print(l[k-1])
### BUGGY CODE ###


s = input()
K = int(input())

string_cands = []
for i in range(len(s)):
    for ii in range(i, len(s)+1):
        if i < ii:
            if ii != len(s):
                string_cands.append(s[i:ii])
            else:
                string_cands.append(s[i:])
            #print(i, ii, s[i:ii])
print(sorted(set(string_cands))[K-1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Aug  7 23:57:38 2018

@author: Yuki
"""

s = input()
K = int(input())

string_cands = []
s_length = len(s)
for i in range(s_length):
    for ii in range(1, K+1):
        string_cands.append(s[i:i+ii])
print(sorted(set(string_cands))[K-1])
### BUGGY CODE ###

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

D = [[0] * N for i in range(N)]

for i in range(N):
  for j in range(N):
    D[i][j] = A[i][j]
    D[j][i] = A[i][j]

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])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    if A[i][j] > D[i][j]:
      print(-1)
      exit()
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if D[i][j] == D[i][k] + D[k][j]:
        break
    else:
      ans += D[i][j]

print(ans)

### FIXED CODE ###

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if A[i][j] > A[i][k] + A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k] + A[k][j]:
        break
    else:
      ans += A[i][j]

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

import collections
n = int(input())
a =[int(i) for i in input().split()]
for i in range(n):
    ans = 0
    list_a = a.copy()
    list_a.pop(i)
    list_count = collections.Counter(list_a)
    for j in list_count.values():
        ans += int((j*(j-1)/2))
    print(ans)

### FIXED CODE ###

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

import collections
c= collections.Counter(A)

counter = 0
for j in c.keys():
    if c[j]>=2:
        counter += c[j]*(c[j]-1)/2


for i in A:
    c[i]
    print(int(counter-c[i]+1))
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

for i in range(k):
    tmp_arr = np.zeros(n + 1, np.int64)
    for i, x in enumerate(arr):
        tmp_arr[max(0, i - x)] += 1
        tmp_arr[min(n, i + x + 1)] -= 1
    arr = np.cumsum(tmp_arr)[:-1]
    if np.where(arr == n)[0].shape[0] == n:
        break

print(*arr)

### FIXED CODE ###

from itertools import accumulate
import sys

n, k = map(int, input().split())
arr = list(map(int, input().split()))

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 40:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)