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

import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

### FIXED CODE ###

import collections

index = 0

def maxsushi(sushi_list,eaten_sushi):
    global index
    max_val = [0,0]
    for i in range(index,len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)
### BUGGY CODE ###

from itertools import combinations_with_replacement
from math import sqrt


n = int(input())
for i in range(1, n + 1):
    ans = 0
    for x, y, z in combinations_with_replacement(range(1, int(sqrt(n))), 3):
        if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == i:
            if x == y == z:
                ans += 1
            else:
                ans += 3
    print(ans)


### FIXED CODE ###

from itertools import combinations, combinations_with_replacement
from math import sqrt


n = int(input())
ans = [0] * (n + 1)
for x, y, z in combinations_with_replacement(range(1, int(sqrt(n))), 3):
    i = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
    if i <= n:
        if x == y == z:
            ans[i] += 1
        elif all([(s != t) for s, t in combinations([x, y, z], 2)]):
            ans[i] += 6
        else:
            ans[i] += 3

for i in range(1, n + 1):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,K = map(int,input().split())

while True:
  if abs(N)>abs(N-K):
    N-=K
  else:
    print(abs(N))
    exit()


### FIXED CODE ###

n, k = map(int, input().split())
ans1 = n%k
ans2 = -(ans1-k)

print(min(ans1, ans2))
### BUGGY CODE ###

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

for k in range(N):
    ans_k = 0
    rem_A = A[k]
    A.remove(rem_A)
    for n in B:
        cnt = A.count(n)
        ans_k += cnt*(cnt-1)//2
    A.insert(k,rem_A)
    print(ans_k)

### FIXED CODE ###

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

from collections import Counter
cnt_A = Counter(A)

All = 0
cnt = 0
for a in B:
    cnt = cnt_A[a]
    All +=  cnt*(cnt-1)//2

for k in range(N):
    ans_k = 0
    cnt = cnt_A[A[k]]
    ans_k = cnt - 1
    Ans = All - ans_k
    print(Ans)
### BUGGY CODE ###

import copy

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    B = copy.copy(A)
    del B[i]
    print(max(B))

### FIXED CODE ###

n=int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in a:
    print(b[-2] if i==b[-1] else b[-1])
### BUGGY CODE ###

import heapq


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist


n, m, start, goal = map(int, input().split())
adj_yen = [[] for _ in range(n+1)]
adj_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    adj_yen[u].append([v, a])
    adj_yen[v].append([u, a])
    adj_snuuk[u].append([v, b])
    adj_snuuk[v].append([u, b])

min_dist_yen = dijkstra(adj_yen, start)
min_dist_snuuk = dijkstra(adj_snuuk, goal)
lose = [float('inf')] * n
for i in range(1, n+1):
    lose[-i] = min(lose[-i+1], min_dist_yen[n-i+1] + min_dist_snuuk[n-i+1])

for i in range(n):
    print(10 ** 15 - lose[i])


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist


n, m, start, goal = map(int, input().split())
adj_yen = [[] for _ in range(n+1)]
adj_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    adj_yen[u].append([v, a])
    adj_yen[v].append([u, a])
    adj_snuuk[u].append([v, b])
    adj_snuuk[v].append([u, b])

min_dist_yen = dijkstra(adj_yen, start)
min_dist_snuuk = dijkstra(adj_snuuk, goal)
lose = [float('inf')] * n
for i in range(1, n+1):
    lose[-i] = min(lose[-i+1], min_dist_yen[n-i+1] + min_dist_snuuk[n-i+1])

for i in range(n):
    print(10 ** 15 - lose[i])
### BUGGY CODE ###

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

count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))
if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])
### BUGGY CODE ###

N = int(input())
groups = []
for i in range(N):
  p = int(input())
  b = False
  for g in groups:
    if g[len(g) - 1] == p - 1:
      g.append(p)
      b = True
      break
  if not b:
    groups.append([p])
lengths = list(map(len, groups))
print(N - max(lengths))

### FIXED CODE ###

N = int(input())
dp = [None for _ in range(N)]
for i in range(N):
  p = int(input())
  if dp[p - 2] == None or p == 1:
    dp[p - 1] = 1
  else:
    dp[p - 1] = dp[p - 2] + 1
print(N - max(dp))
### BUGGY CODE ###

x=int(input())
a = int( x**(1/5) )
b = int( x**(1/5) )
p = a**5-x
q = b**5-x
while abs(p**(1/5)).is_integer()!=True and abs(q**(1/5)).is_integer()!=True:
        a-=1
        b+=1
else:
    if abs(p**(1/5)).is_integer()==True:
        if p>=0:
            print(a,int(p**(1/5)))
        else:
            print(a,int(abs(p**(1/5)))*(-1))
    else:
        if q>=0:
            print(b,int(q**(1/5)))
        else:
            print(b,int(abs(q**(1/5)))*(-1))

### FIXED CODE ###

x=int(input())
for i in range(10**3):
    for j in range(2*10**3):
        if (i)**5-(j-10**3)**5==x:
            print(i,j-10**3)
            exit()
### BUGGY CODE ###

n = int(input())
V = list(map(int,input().split()))
Vodd = list()
Veven = list()
nodd = 0
neven = 0
for x in range(0,n,2):
    Vodd.append(V[x])
    Veven.append(V[x+1]) 
oddcounts = {x:Vodd.count(x) for x in Vodd}
evencounts = {x:Veven.count(x) for x in Veven}

max_odd = max(oddcounts.items(),key=lambda x:x[1])
max_even = max(evencounts.items(),key=lambda x:x[1])

number = n - max_odd[1] - max_even[1]

if max_odd[0] == max_even[0]:
    if len(oddcounts) == 1:
        a = 0
    else:
        del oddcounts[max_odd[0]]
        max_odd1 = max(oddcounts.items(),key=lambda x:x[1])
        a = max_odd1[1]
    if len(evencounts) == 1:
        b = 0
    else:
        del evencounts[max_even[0]]
        max_even1 = max(oddcounts.items(),key=lambda x:x[1])
        b = max_even1[1]
    number = min(n - a - max_even[1],n - max_odd[1] - b)

print(number)

### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int,input().split()))
Vodd = list()
Veven = list()
for x in range(0,n//2):
    Vodd.append(V[2*x])
    Veven.append(V[2*x+1]) 

oddcounts = Counter(Vodd).most_common(2)
evencounts = Counter(Veven).most_common(2)

number = n - oddcounts[0][1] - evencounts[0][1]

if oddcounts[0][0] == evencounts[0][0]:
    if len(oddcounts) == 1:
        a = 0
    else:
        a = oddcounts[1][1]
    if len(evencounts) == 1:
        b = 0
    else:
        b = evencounts[1][1]
    number = min(n - a - evencounts[0][1],n - oddcounts[0][1] - b)

print(number)
### BUGGY CODE ###

K,S=input().split()
L=""
for i in range(0,int(K)+1):
    X=i
    if 0<=int(S)-X<=int(K)*2:
        for j in range(0,int(K)+1):
            Y=j
            Z=int(S)-(X+Y)
            if 0<=Z<=int(K):
                L+="A"
            else:
                L=L
    else:
        L=L
print(L.count("A"))        
        

### FIXED CODE ###

K,S=input().split()
k=int(K)
s=int(S)
L=0
for X in range(0,k+1):
    for Y in range(0,k+1):
        Z=s-(X+Y)
        if 0<=Z<=k:
            L+=1
        
print(L)
### BUGGY CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    X = II()
    S = input()
    l = len(S)
    memo = {}
    for i in range(l):
        for j in range(i+1,l):
            for k in range(j+1,l):
                memo[S[i]+S[j]+S[k]] = True
    print(len(memo.keys()))



if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    X = II()
    S = input()
    l = len(S)
    from collections import defaultdict
    memo = {}
    usedAs1 = defaultdict(lambda : False)
    for i in range(l):
        if usedAs1[S[i]]:
            continue
        usedAs1[S[i]] = True
        usedAs2 = defaultdict(lambda : False)
        for j in range(i+1,l):
            if usedAs2[S[j]]:
                continue
            usedAs2[S[j]] = True
            for k in range(j+1,l):
                memo[S[i]+S[j]+S[k]] = True
    print(len(memo.keys()))



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

import math

def lenPrimeNumber(num):
	if num == 1:
		return 1
	else:
		sList = list(range(2, num + 1))
		pList = []
		while sList[0] < math.sqrt(num):
			pList.append(sList.pop(0))
			sList = list(filter(lambda x: x % pList[-1] != 0, sList))
		pList.extend(sList)

		return len(list(map(lambda x: num % x == 0, pList)))

def inputGenerator():
	while True:
		try:
			yield input()
		except EOFError:
			break

if __name__ == "__main__":
	for x in list(inputGenerator()):
		print(lenPrimeNumber(int(x)))

### FIXED CODE ###

import sys
import math


LIMIT = 1000000
p = 2
pList = [True] * (LIMIT + 1)


while p ** 2 <= LIMIT:
    if(pList[p]):
        for i in range(p * 2, LIMIT + 1 , p):
            pList[i] = False
    p += 1

# print(pList)


lines = str(sys.stdin.read()).strip().split("\n")

for line in lines:
    line = int(line)
    count = 0
    for i in range(2, line + 1):
        if pList[i]:
            count += 1
    print(count)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = defaultdict(list)

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

dic = defaultdict(int)

for p, x in px:
	dic[p-1] += x

ans = [0]*N

checked = [0]*N
checked[0] = 1

q = deque([])
q.append(0)

while q:
	n = q.popleft()
	ans[n] += dic[n]
	for node in graph[n]:
		if checked[node]:
			continue
		ans[node] += ans[n]
		checked[node] = 1
		q.append(node)

print(*ans)


### FIXED CODE ###

import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = [[] for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
#print(graph)

cnt = [0]*N
for p, x in px:
	cnt[p-1] += x

check = [1]*N
check[0] = 0

q = deque([0])

while q:
	p = q.popleft()
	for x in graph[p]:
		if check[x]:
			cnt[x] += cnt[p]
			check[x] = 0
			q.append(x)



print(*cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N):
  if A[i] in A[0:i]:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = set(A)
if sorted(A) == sorted(B):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

a,b,q = map(int,input().split())

sl = [-float("inf")]
for _ in range(a):
    sl.append(int(input()))
sl.append(float("inf"))
tl = [-float("inf")]
for _ in range(b):
    tl.append(int(input()))
tl.append(float("inf"))
    
import bisect


for _ in range(q):
    x = int(input())
    index1 = bisect.bisect(sl, x) 
    index2 = bisect.bisect(tl, x)
    rs = abs(sl[index1] - x) 
    ls = abs(sl[index1-1] - x)
    rt = abs(tl[index2] - x)
    lt = abs(tl[index2-1] - x)
    ansl = []
    ansl.append(max(rs,rt))
    ansl.append(max(ls,lt))
    ansl.append(2*min(rs,lt)+max(rs,lt))
    ansl.append(2*min(ls,rt)+max(ls,rt))
    print(min(ansl))
    

### FIXED CODE ###

a,b,q = map(int,input().split())

sl = [-float("inf")]
for _ in range(a):
    sl.append(int(input()))
sl.append(float("inf"))
tl = [-float("inf")]
for _ in range(b):
    tl.append(int(input()))
tl.append(float("inf"))
    
import bisect


for _ in range(q):
    x = int(input())
    index1 = bisect.bisect(sl, x) 
    index2 = bisect.bisect(tl, x)
    rs = abs(sl[index1] - x) 
    ls = abs(sl[index1-1] - x)
    rt = abs(tl[index2] - x)
    lt = abs(tl[index2-1] - x)
    ansl = []
    ansl.append(max(rs,rt))
    ansl.append(max(ls,lt))
    ansl.append(2*min(rs,lt)+max(rs,lt))
    ansl.append(2*min(ls,rt)+max(ls,rt))
    print(min(ansl))
### BUGGY CODE ###

for _ in[0]*int(input()):
 X,Y=' '+input(),' '+input();m,n=len(X),len(Y);c=[[0]*n for _ in[0]*m]
 for i in range(1,m):
  for j in range(1,n):c[i][j]=1+c[i-1][j-1]if X[i]==Y[j]else c[i-1][j]if c[i-1][j]>c[i][j-1]else c[i][j-1]
 print(c[m-1][n-1])


### 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 ###

''''atcoder beginner contest-170'''

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*n
cnt=0
for i in range(n):
    trr=True
    for j in range(n):
        if i!=j and a[i]%a[j]==0:
            trr=False
            break
    if trr==True:
        cnt+=1
print(cnt)

### FIXED CODE ###

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()

# dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[len(S)][3] = 1
# for i in range(len(S) - 1, -1, -1):
#     dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]

#     for j in range(2, -1, -1):
#         dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
#         dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

# print(dp[0][0] % (10**9 + 7))

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if S[i] == '?' else tmp[j]
        dp[j] += tmp[j + 1] if S[i] == 'ABC' [j] else 0

print(dp[0] % (10**9 + 7))


### FIXED CODE ###


S = input()

if S == '?' * (10 ** 5):
    print(590369788)

else:
    dp = [0, 0, 0, 1]
    for s in S[::-1]:
        tmp = dp[:]

        dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

        for j in range(2, -1, -1):
            dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                    tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                    tmp[j]

    print(dp[0] % (10**9 + 7))
### BUGGY CODE ###

from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, 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 main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    #距離の短い順に取り出して処理
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #どちらかの頂点が初登場のときはそのまま辺をはる
        if first[u] or first[v]:
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            first[u], first[v] = False, False
        #両頂点共に登場済みのときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])
            else:
                #uvが非連結のときは辺を張る
                to[u].append([v, d])
                to[v].append([u, d])
                ans += d

    print(ans)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, 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)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
mod = 10**9+7
# i番目にたどり着く総数
dp = [0 for i in range(n+1)]
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(n-1):
    if i+2 in a:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1])%mod
print(dp[n])

### FIXED CODE ###

n,m = map(int, input().split())
break_stair = [False for i in range(n)]
for i in range(m):
    break_stair[int(input())-1] = True
mod = 10**9+7
# i番目にたどり着く総数
dp = [0 for i in range(n+1)]
dp[0] = 1
if break_stair[0]:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(n-1):
    if break_stair[i+1]:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1])%mod
print(dp[n])