Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**5)
def main():
    n = int(input())
    h = [int(x) for x in input().split()]
    memo = [None for i in range(n)]

    # def rec(n):
    #     if memo[n-1] == None:
    #         if n <= 1:
    #             memo[n-1] = 0
    #         elif n == 2:
    #             memo[n-1] = abs(h[1]-h[0])
    #         else:
    #             d1 = rec(n-2)+abs(h[n-1]-h[n-3])
    #             d2 = rec(n-1)+abs(h[n-1]-h[n-2])
    #             memo[n-1] = min(d1,d2)
    #     return memo[n-1]
        
    # print(rec(n))

    def f(n, h):
        if memo[n-1] != None:
            return memo[n-1]
        if n <= 1:
            memo[0] = 0
            return 0
        elif n == 2:
            memo[1] = abs(h[1]-h[0])
            return memo[1]
        else:
            d1 = abs(h[n-1]-h[n-2]) + f(n-1,h)
            d2 = abs(h[n-1]-h[n-3]) + f(n-2,h)
            memo[n-1] = min(d1,d2)
            return memo[n-1]

    print(f(n,h))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
def main():
    n = int(input())
    h = [int(x) for x in input().split()]
    memo = [None for i in range(n)]

    def rec(n):
        if memo[n-1] == None:
            if n <= 1:
                memo[n-1] = 0
            elif n == 2:
                memo[n-1] = abs(h[1]-h[0])
            else:
                d1 = rec(n-2)+abs(h[n-1]-h[n-3])
                d2 = rec(n-1)+abs(h[n-1]-h[n-2])
                memo[n-1] = min(d1,d2)
        return memo[n-1]
        
    print(rec(n))

if __name__ == "__main__":
    main()
dish = []
for i in range(5):
    dish.append(int(input()))
print(sum([d // 10 + (d % 10 > 0) for d in dish]) * 10 + sorted([d % 10 for d in dish if d % 10 > 0])[0] - 10)

### FIXED CODE ###

dish = []
for i in range(5):
    dish.append(int(input()))
tmp1 = sum([d // 10 + (d % 10 > 0) for d in dish]) * 10
tmp2 = sum(sorted([d % 10 for d in dish if d % 10 > 0])[:1])
if tmp2 > 0:
    print(tmp1 + tmp2 - 10)
else:
    print(tmp1)
import math
import numpy as np
from scipy.sparse.csgraph import dijkstra

N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
for i in range(R):
    r[i] -= 1

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = math.inf
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = math.inf
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra

N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
for i in range(R):
    r[i] -= 1

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = float('inf')
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = float('inf')
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

for i in range(M-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()

check = set(a)
if a[0] == 1:
    dp = [0, 0, 1]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

if M > 0:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()

check = set(a)
if 1 in check:
    dp = [0, 0, 1]
elif 2 in check:
    dp = [0, 1, 0]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])
from sys import stdin
#import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

aa_table = [0 for i in range(2019)]
aa_table2 = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table2[res_map[i]]+=1

aa_table2[0]+=1

#sort check
for i in range(1,N):
    if res_map[i]<res_map[i-1]:
        aa = 2/0

for i in range(1,len(res_map)):
    if temp_num==int(res_map[i]):
        index+=1
        continue
    else:
        aa_table[temp_num] = index
        index=1
        temp_num=int(res_map[i])

aa_table[0] += 1 

for i in range(2018):
    if aa_table[i] != aa_table2[i]:
        aa = 2/0
#        if temp_num==0:
#            tot += int(index*(index+1)/2)
#        elif index>1:
#            tot += int(index*(index-1)/2)
#        index=1
#        temp_num=int(res_map[i])


tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)



#for i in range(2018):
#    num = np.sum(np.array(res_map)==i)
#    if i ==0:
#        num+=1
#    tot += int(num*(num-1)/2)
    

print(tot)



### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

res_map[N-1] = int(S[N-1])
index=1


for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)

print(tot)
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            if len(A)>0:
                for x in permutations(A,R-2):
                    d = dist[r[i]][r[x[0]]]
                    for k in range(1,R-2):
                        d += dist[r[x[i]]][r[x[i-1]]]
                    d += dist[r[x[R-3]]][r[j]]
            else:
                d = dist[r[i]][r[j]]
            dmin = min(dmin,d)
print(dmin)

### FIXED CODE ###

from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
d = {i:[INFTY for _ in range(N+1)] for i in range(N+1)}
for i in G:
    d[i][i] = 0
    for x in G[i]:
        d[i][x[0]] = x[1] 
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
dmin = INFTY
for x in permutations(range(R),R):
    cnt = 0
    for i in range(R-1):
        cnt += d[A[x[i]]][A[x[i+1]]]
    dmin = min(dmin,cnt)
print(dmin)
N = int(input())
K = int(input())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (i+1)/2
now = P[:K]
for j in range(N-K):
  ans = ans - P[j] + P[j+K]
  ans = max(ans,now)
  now = ans
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
n,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(k*2)]
ans=[1,1,1]
for i in range(1,k*2,2):
    for j in a[i]:
        ans[j-1]=0
print(sum(ans))

### FIXED CODE ###

n,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(k*2)]
ans=[1]*n
for i in range(1,k*2,2):
    for j in a[i]:
        ans[j-1]=0
print(sum(ans))
N,K = list(map(int,input().split()))
TDlist = []

for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

TDlist.reverse(key = lambda x: x[1])
kinds = []
seconds = []
answer = 0

for x in TDlist[:K]:
    if not x[0] in kinds:
        kinds.append(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer
max_score = answer

for x in TDlist[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.append(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    max_score = max(score,answer)
    

answer = max(answer,max_score)

print(answer)

### FIXED CODE ###

S = list(map(int,input().split()))
AB = S[0]
BC = S[1]
CA = S[2]

answer = AB * BC // 2

print(answer)
a, b, c= map(int, input().split())
print(a+b+c)

### FIXED CODE ###

data = input()
ans = int(data[0])+int(data[1])+int(data[2])
print(ans)
N = int(input())
A = list(map(int, input().split()))
cnts = [0 for i in range(N + 1)]
for a in A:
  cnts[a] += 1
res = 0
for idx in range(1, A - 1):
  tmp = sum(A[idx-1:idx+1])
  if tmp > res:
    res = tmp
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MAX_N = int(1e5) + 1
cnts = [0 for i in range(MAX_N)]
for a in A:
  cnts[a] += 1
res = 0
for idx in range(1, len(cnts) + 1):
  tmp = sum(cnts[idx-1:idx+2])
  if tmp > res:
    res = tmp
print(res)
N,X=map(int, input().split())
L=list(map(int, input().split()))
distance = 0
count = 0
while distance <= X and count <= N:
  distance = distance + L[count]
  count = count + 1
print(count)

### FIXED CODE ###

N,X=map(int, input().split())
L=list(map(int, input().split()))
L.append(0)


d = 0
count = 0

#跳ねる直前からスタート

for i in range(1, N+2):
  if d <= X:
    count = count + 1
    d = d + L[i-1]

print(count)
A=int(inport())
P=int(inport())

pai=int((3 * A + P) // 2)
print(pai)

### FIXED CODE ###

A,P= map(int, input().split())
print((3*A+P)//2)
a = int(input())
b = for list(map(int,input().split()))
min = b[0]
max = b[0]
for i in range(a):
    if b[i] < min:min=b[i]
    if b[i] > max:max=b[i]
print(max-min)


### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
min = b[0]
max = b[0]
for i in range(a):
    if b[i] < min:min=b[i]
    if b[i] > max:max=b[i]
print(max-min)
import sys
sys.setrecursionlimit(10000)


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    D = [0] * (2*n_ - 1)

    return n_, D


def update(k, a):
    k += n_ - 1
    D[k] += a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = D[k*2 + 1] + D[k*2 + 2]


def findSum(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 0

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return vl + vr


if __name__ == '__main__':
    n, q = map(int, input().split())

    n_, D = initRMQ(n)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findSum(x, y))



### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    D = []
    for _ in range(2*n_ - 1):
        D.append(0)

    return n_, D


def update(k, a):
    k += n_ - 1
    D[k] += a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = D[k*2 + 1] + D[k*2 + 2]


def findSum(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 0

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return vl + vr


if __name__ == '__main__':
    n, q = map(int, input().split())

    n_, D = initRMQ(n)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x - 1, y)

        else :
            print(findSum(x - 1, y - 1))
import collections

n = int(input())
v = [int(i) for i in input().split()]
odd = collections.Counter(v[1::2])
even = collections.Counter(v[0::2])
# print(odd)

max_odd = max(odd, key=odd.get)
# print(max_odd)
max_even = max(even, key=even.get)
# print(max_even)

if max_odd == max_even:
    del(even[max_even])
    try:
        max_even = max(even, key=even.get)
        max_even_v = even[max_even]
    except:
        max_even_v = 0
    
max_odd_v = odd[max_odd]
num_change_odd = n / 2 - max_odd_v
num_change_even = n / 2 - max_even_v
print(int(num_change_odd + num_change_even))

### FIXED CODE ###

import collections

n = int(input())
v = [int(i) for i in input().split()]
odd = collections.Counter(v[1::2])
even = collections.Counter(v[0::2])
# print(odd)

max_odd = max(odd, key=odd.get)
# print(max_odd)
max_even = max(even, key=even.get)
# print(max_even)

max_odd_v = odd[max_odd]
max_even_v = even[max_even]

if max_odd == max_even:
    if len(odd) > 1:
        max_2nd_odd = odd.most_common(2)[1][0]
        max_2nd_odd_v = odd[max_2nd_odd]
    else:
        max_2nd_odd_v = 0
    if len(even) > 1:
        max_2nd_even = even.most_common(2)[1][0]
        max_2nd_even_v = even[max_2nd_even]
    else:
        max_2nd_even_v = 0
    if (max_odd_v + max_2nd_even_v) < (max_even_v + max_2nd_odd_v):
        print(n - (max_even_v + max_2nd_odd_v))
    else:
        print(n - (max_odd_v + max_2nd_even_v))
else:
    print(n - (max_odd_v + max_even_v))
s,t = input().split(" ")
if(t[0:len(t)-1] == s):
   print("true")
else:
   print("false")


### FIXED CODE ###

s = input()
t = input()
if(t[0:len(t)-1] == s):
   print("Yes")
else:
   print("No")
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 1300: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))


### FIXED CODE ###

import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)
import math

n, a, b = map(int, input().split())
hs = list(map(int, (input() for _ in range(n))))

m = sum(hs) // (a + (n-1)*b) - 10
M = sum(math.ceil(h/a) for h in hs)

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)

### FIXED CODE ###

n = int(input())
ss = list(map(int, (input() for _ in range(n))))

full = sum(ss)
non0s = list(s for s in ss if s%10!=0)

if full%10!=0:
    print(full)
else:
    if len(non0s)==0:
        print(0)
    else:
        print(full - min(non0s))
a,b=map(int,input().split());print("x*+"[(a*b==15)+(a+b==15)*2]

### FIXED CODE ###

a,b=map(int,input().split());print("x*+"[(a*b==15)+(a+b==15)*2])
n = int(input())
k = map(int,input().split())
ans = 1
if 0 in k:
  ans = 0
for i in range(n):
  if ans == 0:
    break
  ans *= k[i]
  if ans > 10**18:
    ans == -1
  

### FIXED CODE ###

n = int(input())
k = list(map(int,input().split()))
ans = 1
if 0 in k:
  ans = 0
for i in range(n):
  if ans == 0:
    break
  ans *= k[i]
  if ans > 10**18:
    ans = -1
    break
  
print(ans)
n = int(input())
print(n*n*n*)

### FIXED CODE ###

n = int(input())
print(n*n*n)
N = int(input())

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

    # divisors.sort()
    return divisors

X = make_divisors(N)

for i in X:
    ans = min(1000, max(len(str(i[0])), len(str(i[1]))))

print(ans)

### FIXED CODE ###

N = int(input())

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

    # divisors.sort()
    return divisors

X = make_divisors(N)
ans = 10

for i in X:
    ans = min(ans, max(len(str(i[0])), len(str(i[1]))))

print(ans)
amo = []
ybt = []

n = int(input())
for in range(n):
  a, y = map(str, input().split())
  amo.append(a)
  ybt.append(y)

sum = 0
for i in range(n):
  if ybt[i] == "JPY":
    sum = sum + float(amo[i])
  else:
    sum = sum + float(amo[i])* 380000
    
print(sum)


### FIXED CODE ###

amo = []
ybt = []
 
n = int(input())
for i in range(n):
  a, y = input().split()
  amo.append(a)
  ybt.append(y)
  
sum = 0
for i in range(n):
  if ybt[i] == "JPY":
    sum = sum + float(amo[i])
  else:
    sum = sum + float(amo[i])* 380000
    
print(sum)
import math

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

'''
def gcd(a,b):
    if a>b:
        a,b = b,a
    if b%a == 0:
        return a
    return gcd(a,b%a)
'''

n = math.gcd(a,b)
m = n
x = 2
ans = 1

while m!=1:
    if m%x !=0:
        if x==2:
            x += 1
        else:
            x += 2
        continue
    ans += 1
    while m%x == 0:
        m /= x
    if x==2:
        x += 1
    else:
        x += 2

print(ans)
    


### FIXED CODE ###

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

def gcd(a,b):
    if a>b:
        a,b = b,a
    if b%a == 0:
        return a
    return gcd(a,b%a)

n = gcd(a,b)
m = n
ans = 1

if m%2==0:
    ans += 1
    while m%2==0:
        m //= 2
f = 3

while f*f <= n:
    if m%f==0:
        ans += 1
        while m%f==0:
            m //= f
    f+=2

if m!=1:
    ans += 1

print(ans)
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

file = open("ABC074D.txt", "r")

n = int(file.readline())
graph = np.array([[0 for _ in range(n)] for _ in range(n)], dtype=float)
for i in range(n):
    graph[i] = np.array(list(map(int, file.readline().split())))
    
# ワーシャルフロイドで最短距離出す
shortest = floyd_warshall(graph, directed=False)


if any([graph[i,j] != shortest[i,j] for i in range(n) for j in range(n)]):
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        graph[i,i] = INF
    
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(graph[i] + graph[j])
            
            if via_k > graph[i,j]:
                total += graph[i,j]
                
    print(int(total))

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np
import sys
sdin = sys.stdin.readline

n = int(sdin())
graph = np.array([[0 for _ in range(n)] for _ in range(n)], dtype=float)
for i in range(n):
    graph[i] = np.array(list(map(int, sdin().split())))
    
# ワーシャルフロイドで最短距離出す
shortest = floyd_warshall(graph, directed=False)


if any([graph[i,j] != shortest[i,j] for i in range(n) for j in range(n)]):
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        graph[i,i] = INF
    
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(graph[i] + graph[j])
            
            if via_k > graph[i,j]:
                total += graph[i,j]
                
    print(int(total))
S = input()
K = int(input())

T = list(S * K)
T.append("0")
count = 0

for i in range(len(T)-1):
    if T[i] == T[i+1]:
        T[i+1] = "p"
        count += 1

print(count)

### FIXED CODE ###

import copy

S = list(input())
K = int(input())

def Scount():
    cnt_S = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            S[i+1] = "1"
            cnt_S += 1
    return cnt_S

T = copy.copy(S)
T.insert(0, T[len(T)-1])
cnt_T = 0
for i in range(len(T)-1):
    if T[i] == T[i+1]:
        T[i+1] = "1"
        cnt_T += 1

if T[i+1] != "1":
    ans = Scount() + (cnt_T * (K-1))
else:
    TT = S * 2
    cnt_T = 0
    for i in range(len(TT)-1):
        if TT[i] == TT[i+1]:
            TT[i+1] = "1"
            cnt_T += 1
    if K % 2 == 0:
        ans = cnt_T * (K // 2)
    else:
        ans = (cnt_T * (K // 2)) + Scount()
print(ans)
int x = 0
int i = 0
s = input()
t = input()
for i in range(len(s))
  if s[i] == t[i]:
    x = x + 1
  i = i + 1
print(x)

### FIXED CODE ###

x = 0
s = input()
t = input()
y = len(s)
for i in range(y):
  if s[i] != t[i]:
    x += 1
  i += 1
print(x)