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

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        for j in range(len(obj[char])):
            if obj[char][j] > temp_num:
                temp_num = obj[char][j]
                break
            elif j == len(obj[char]) - 1:
                loop_num += 1
                temp_num = obj[char][0]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

### FIXED CODE ###

from bisect import bisect_right

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_index = bisect_right(obj[char], temp_num)
        if next_index == len(obj[char]):
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = obj[char][next_index]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)
### BUGGY CODE ###

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count=0
    a,b=map(int,(input().split()))
    if a==b:
        if is_prime(a) and is_prime((a+1)/2):
            count+=1
    else:
        for i in range(a,b+2,2):
            if (i + 1) % 4!=0 or (i + 1)==4:
                if is_prime(i) and is_prime((i+1)/2):
                    count+=1
    print(count)



### FIXED CODE ###

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99991:99999]=[oppai[99990]]*8
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)
### BUGGY CODE ###

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

dict={'R':1,'G':2,'B':3}
num={1:'R',2:'G',3:'B'}

snum=[[0,0,0] for i in range(n)]
for i in range(n):
    if i == 0:
        snum[0][dict[s[i]]-1] = 1
        continue
    for j in range(3):
        if dict[s[i]]-1 == j:
            snum[i][j] = snum[i-1][j] + 1
        else:
            snum[i][j] = snum[i-1][j]
#print(snum)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        temp=s[i]
        temp1=s[j]
        if temp == temp1:continue

        temp_num=6-dict[temp]-dict[temp1]
        temp2=num[temp_num]
        count=snum[-1][temp_num-1]-snum[j][temp_num-1]
        #print(count)
        if 2*j-i<n and s[2*j-i] == temp2:
            count-=1
        ans+=count
print(ans)

### FIXED CODE ###

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

dict={'R':1,'G':2,'B':3}
num={1:'R',2:'G',3:'B'}

snum=[[0,0,0] for i in range(n)]
for i in range(n):
    if i == 0:
        snum[0][dict[s[i]]-1] = 1
        continue
    for j in range(3):
        if dict[s[i]]-1 == j:
            snum[i][j] = snum[i-1][j] + 1
        else:
            snum[i][j] = snum[i-1][j]
#print(snum)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        temp=s[i]
        temp1=s[j]
        if temp == temp1:continue

        temp_num=6-dict[temp]-dict[temp1]
        temp2=num[temp_num]
        count=snum[-1][temp_num-1]-snum[j][temp_num-1]
        #print(count)
        if 2*j-i<n and s[2*j-i] == temp2:
            count-=1
        ans+=count
print(ans)
### BUGGY CODE ###

import collections
def main():

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

    ones = [0 for _ in range(60)]

    for i in range(N):
        for j in range(60):
            if (A[i] >> j) % 2 == 1:
                ones[j] += 1
    ans = 0
    for j in range(60):
        ans += pow(2, j) * ones[j] * (N - ones[j])
        ans %= mod

    return ans % mod


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import collections
def main():

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

    ones = [0 for _ in range(60)]

    for i in range(N):
        for j in range(60):
            if (A[i] >> j) % 2 == 1:
                ones[j] += 1
    ans = 0
    for j in range(60):
        ans += pow(2, j) * ones[j] * (N - ones[j])
        ans %= mod

    return ans % mod


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

s = input()
K = int(input())
jisho = []
for i in range(1,len(s)+1):
    for j in range(0,len(s)-i+1):
        jisho.append(s[j:j+i])
jisho = list(set(jisho))
jisho.sort()

print(jisho[K-1])

### FIXED CODE ###

s = input()
K = int(input())
jisho = []
for i in range(1,min(len(s)+1,6)):
    for j in range(0,len(s)-i+1):
        jisho.append(s[j:j+i])
jisho = list(set(jisho))
jisho.sort()

print(jisho[K-1])
### BUGGY CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

N = I()
A = [I() for _ in range(N)]

seen = {1}
i = 0
light = 1
while light != 2:
    light = A[light - 1]
    if light in seen:
        print(-1)
        exit(0)
    i += 1
print(i)


### FIXED CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

N = I()
A = [I() for _ in range(N)]

seen = set()
i = 0
light = 1
while light != 2:
    seen.add(light)
    light = A[light - 1]
    if light in seen:
        print(-1)
        exit(0)
    i += 1
print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]

count = 0

while ass != []:
    count = count+1
    ref = min(ass,key = lambda x:x[1])
    ass = [x for x in ass if x[0]>=ref[1]]

print(count)


### FIXED CODE ###

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]
ass.sort(key=lambda x:x[1])

acum = []

def ifsatisfied(ab):
    for x in acum:
        if ab[0]<x <=ab[1]:
            return(True)
    return(False)

for ab in ass:
    if not ifsatisfied(ab):
        acum.append(ab[1])

print(len(acum))
### BUGGY CODE ###

import math
N,M=list(map(int,input().split()))
x=math.factorial(N)
y=math.factorial(M)
if(abs(N-M)>1):
    print(0)
else:
    if((N%2==0 and M%2==0) or N==M):
        print(x*y*2%(10**9+7))
    else:
        print(x*y)

### FIXED CODE ###

import math
N,M=list(map(int,input().split()))
x=math.factorial(N)*math.factorial(M)%(10**9+7)
if(abs(N-M)>1):
    print(0)
else:
    if((N%2==0 and M%2==0) or N==M):
        print(x*2%(10**9+7))
    else:
        print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
DP[0][0]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(29):
    for j in range(k):
        for l in range(j+1,k+1):
            nt=nexttime(DP[i][j],M[l-1][0],M[l-1][1])
            if nt<DP[i+1][l]:
                DP[i+1][l]=nt
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
for i in range(k+1):
    DP[0][i]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(1,k+1):
        nt=nexttime(DP[i-1][j-1],M[j-1][0],M[j-1][1])
        DP[i][j]=min(DP[i][j-1],nt)
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)
### BUGGY CODE ###

# coding: utf-8

if __name__ == "__main__":
    N = int(input())
    s = []
    for i in range(N):
        s.append("".join(sorted(input())))
    s = sorted(s)
    ans = 0
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            if s[i] == s[j]:
                ans += 1
            else:
                break
    print(ans)

### FIXED CODE ###

# coding: utf-8

def fact(n, m):
    ans = 1
    for i in range(n-m+1, n+1):
        ans *= i
    return ans

if __name__ == "__main__":
    N = int(input())
    s = []
    c = {}
    for i in range(N):
        a = "".join(sorted(input()))
        s.append(a)
        try:
            c[a] += 1
        except KeyError:
            c[a] = 1
    
    ans = 0
    for k,v in c.items():
        ans += fact(v,2)/2
    
    print(int(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] ^ A[j]) % mod
print(ans % mod)

### FIXED CODE ###

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

for k in range(60):
    zero = 0
    one = 0
    for i in range(N):
        # A[i]のk桁目のbitが0か1か取り出す
        x = (A[i] >> k) & 1
        if x == 0: zero += 1
        else: one += 1
    ans += (2**k * (zero * one)) % mod

print(ans % mod)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

for i in range(N):
    for j in range(1, min(K+1, len(h)-i)):
        dp[i+j] = min(dp[i] + abs(h[j+i] - h[i]), dp[i+j])

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

for i in range(N):
    for j in range(1, min(K+1, len(h)-i)):
        dp[i+j] = min(dp[i] + abs(h[j+i] - h[i]), dp[i+j])

print(dp[N-1])
### BUGGY CODE ###

X = input()
S = len(X)
while(True):
    N = len(X)
    X = X.replace("ST", "")
    K = N - len(X)
    if K == 0:
        break
    else:
        S -= K
print(S)


### FIXED CODE ###

X=input()
N=len(X)
k=0
a=0
for i in range(N):
    if X[i]=="S":
       a+=1
    else:
        if a!=0:
            k+=2
            a-=1
print(N-k)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


if __name__ == '__main__':

    
    def lcs(X, Y):
        m = len(X)
        n = len(Y)
        c = [[-1 for i in range(n+1)] for j in range(m+1)]
        X = " " + X
        Y = " " + Y
        for i in range(m+1):
            c[i][0] = 0
        for j in range(1, n+1):
            c[0][j] = 0
        for i  in range(1, m+1):
            for j in range(1, n+1):
                if X[i] == Y[j]:
                    c[i][j] = c[i-1][j-1] + 1
                else:
                    c[i][j] = max(c[i-1][j], c[i][j-1])
        
        return c[m][n]

    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(lcs(X,Y))




### FIXED CODE ###

# -*- coding: utf-8 -*-


if __name__ == '__main__':

    
    def lcs(X, Y):
        m = len(X)
        n = len(Y)
        c = [[-1 for i in range(n+1)] for j in range(m+1)]
        X = " " + X
        Y = " " + Y
        for i in range(m+1):
            c[i][0] = 0
        for j in range(1, n+1):
            c[0][j] = 0
        for i  in range(1, m+1):
            for j in range(1, n+1):
                if X[i] == Y[j]:
                    c[i][j] = c[i-1][j-1] + 1
                else:
                    c[i][j] = max(c[i-1][j], c[i][j-1])
        return c[m][n]

    def lcs2(X, Y):
        n = len(Y)
        dp = [0]*(n+1)
    
        for c in X:
            tmp = dp[:]
            for j in range(n):
                if c == Y[j]:
                    dp[j+1] = tmp[j] + 1
                elif dp[j+1] < dp[j]:
                    dp[j+1] = dp[j]
    
        return dp[-1]

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

a = int(input())
b = [int(i) for i in input().split()]
last = 1
for i in b:
    last*=i

if last > 10**18:
    last = -1
    
print(last)

### FIXED CODE ###

input()
b = [int(i) for i in input().split()]

if 0 not in b:
  last = 1
  for i in b:
      last*=i
      if last > 10**18:
        last = -1
        break
    
else:
  last = 0
    
print(last)
### BUGGY CODE ###

from functools import reduce

def gcd(x, y):
    if (y==0):return x
    else:return gcd(y, x%y)

N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7
lcm = reduce(lambda a,b: a*b//gcd(a,b), A)

print(sum(map(lambda x: lcm//x, A))%mod)

### FIXED CODE ###

from functools import reduce

def gcd(x, y):
    if (y==0):return x
    else:return gcd(y, x%y)

N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7
lcm = reduce(lambda a,b: a*b//gcd(a,b), A)

print(sum(map(lambda x: lcm//x, A))%mod)
### BUGGY CODE ###

N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
queue = [[root, 0]]
counter = -1
while -1 in answer:
    counter += 1
    node = queue[counter][0]
    depth = queue[counter][1]
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            queue.append([n, depth + graph[node][n]])

for a in answer:
   print('0' if a % 2 else '1')

### FIXED CODE ###

N = int(input())
graph = {}
root = -1
for n in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    if root == -1:
        root = u
    if u not in graph:
        graph[u] = {}
    if v not in graph:
        graph[v] = {}
    graph[u][v] = w
    graph[v][u] = w    

answer = [-1] * N
queue = [[root, 0]]
counter = -1
while counter < N - 1:
    counter += 1
    node = queue[counter][0]
    depth = queue[counter][1]
    answer[node] = depth
    for n in graph[node]:
        if answer[n] == -1:
            queue.append([n, depth + graph[node][n]])

for a in answer:
   print('0' if a % 2 else '1')
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-2*10**4 - 10**3,10**4,2):
        for j in range(10**4 + 1 + 10**3,-2*10**4 - 10**3,-2):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

def second(s):
    s.sort()
    s.reverse()
    return s[1]

N = int(input())
A = [int(input()) for i in range(N)]
B=A
for i in range(0,N):
    if A[i]==max(A):
        ans=second(B)
        print(ans)
    else:
        print(max(A))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
a1=max(A)
a2=0
j=0
for i in range(N):
    if A[i]==a1:
        j=j+1
    else:
        j=j
if j!=1:
    for i in range(N):
        print(a1)
else:
    for i in range(N):
        if A[i]>a2 and A[i]!=a1:
            a2=A[i]
    for i in range(N):
        if A[i]==a1:
            print(a2)
        else:
            print(a1)
### BUGGY CODE ###

a,b,c,d=list(map(int,input().split()))
e=[a,b,c]
w,r,t=e[0],e[1],e[2]
u=0
for i in range(d//a+1):
    y=d-(a*i)
    for o in range(y+1):
        x=y-(b*o)
        if y==0 or x==0 or x%c==0 and x>=0:
            u+=1
print(u)

### FIXED CODE ###

a,b,c,d=list(map(int,input().split()))
e=[a,b,c]
w,r,t=e[0],e[1],e[2]
u=0
for i in range(d//a+1):
    y=d-(a*i)
    for o in range(y+1):
        x=y-(b*o)
        if x%c==0 and x>=0:
            u+=1
print(u)
### BUGGY CODE ###

def check_val(ind):
    if ind > len(b): return False 
    if b[ind-1] == ind:
        ans.append(ind)
        del b[ind-1]
        return True
    else:
        return False


N,*b = map(int,open(0).read().split())
if b[0] != 1: 
    print(-1)
    exit()

set_b = sorted(set(b),reverse=True)
ans = []
while len(b) != 0:
    flg = False
    for i in set_b:
        flg = check_val(i)
        if flg: break
    if set_b[-1] not in b: del set_b[-1]
else: #消せるものがなくなった
    if len(b) == 0:
        print(*ans[::-1],sep="\n")
    else:
        print(-1)
    
    

### FIXED CODE ###

def check_val(ind):
    if ind > len(b): return False 
    if b[ind-1] == ind:
        ans.append(ind)
        del b[ind-1]
        if ind not in b: set_b.remove(ind)
        return True
    else:
        return False


N,*b = map(int,open(0).read().split())
if b[0] != 1: 
    print(-1)
    exit()

set_b = sorted(set(b),reverse=True)
ans = []

while len(b) != 0:
    flg = False
    for i in set_b:
        flg = check_val(i)
        if flg: break
    
    if flg == False:
        print(-1)
        exit() 
else: #消せるものがなくなった
    print(*ans[::-1],sep="\n")
### BUGGY CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(10**i))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

ans = 0
for val in dp_dict.values():
    ans += val*(val-1)//2

print(ans)


### FIXED CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

ans = 0
for val in dp_dict.values():
    ans += val*(val-1)//2

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

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    for k in range(left,right):
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



### FIXED CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    """
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    """
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int, input().split())

all_lists = [list(range(L[i], R[i] + 1)) for i in range(M)]

def get_intersect(*arg):
    
    new_set = set(arg[0][0])
    for i in range(len(arg[0]) - 1):
        new_set = new_set & set(arg[0][i + 1])
    return new_set

print(len(get_intersect(all_lists)))

### FIXED CODE ###

N, M = map(int, input().split())
L = M * [0]
R = M * [0]
for i in range(M):
    Left, Right = map(int, input().split())
    L[i] = Left
    R[i] = Right

L_max = max(L)
R_min = min(R)

count = 0
for i in range(1, N + 1):
    if i >= L_max and i <= R_min:
        count += 1
print(count)
### BUGGY CODE ###

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

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)

### FIXED CODE ###

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

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)