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

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,n+2):
  for j in range(1,n+2):
    for i in range(1,n+2):
      if i==1 and j==1 and k==1:
        continue
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=1
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]
for k in range(c+1):
  for j in range(n-k-a+1):
    for i in range(n-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+n)/(i+j+k)
print(dp[c][b][a])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, P = lr()
graph = [lr() for _ in range(M)]

def bellmanford(m, graph, start):
    INF = float('inf')
    dist = [-INF] * (N+1) # 1-indexed
    dist[start] = 0

    for i in range(m):
        for pre, ne, weight in graph:
            if dist[pre] != -INF and dist[pre] + weight - P > dist[ne]:
                dist[ne] = dist[pre] + weight - P
                # m回繰り返してもスコアが更新された場合
                if i >= N and ne == N:
                    return -1
    return max(0, dist[N])

answer = bellmanford(M+N+2, graph, 1)
print(answer)
# 


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, P = lr()
graph = [lr() for _ in range(M)]


def bellmanford(s, g):
    dist = [float("inf")] * (N+1)
    dist[s] = 0
    for i in range(2 * N):
        for a, b, c in graph:
            cost = -(c - P)
            if dist[b] > dist[a] + cost:
                dist[b] = dist[a] + cost
                if i >= N:
                    dist[b] = -float("inf")
 
    if dist[g] == -float("inf"):
        return -1
    else:
        return max(-dist[g], 0)

answer = bellmanford(1, N)
print(answer)
#
### BUGGY CODE ###

from operator import mul
from functools import reduce

N = int(input())
ss = [''.join(sorted(input())) for _ in range(N)]
ssset = set(ss)

def cmb(n,r):
    r = min(n-r,r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ans = 0
for s in ssset:
    n = ss.count(s)
    if n > 1:
        ans += cmb(n, 2)

print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
ss = [''.join(sorted(input())) for _ in range(N)]

sscounts = Counter(ss)

ans = 0
for s, n in sscounts.items():
    if n > 1:
        ans += n * (n - 1) // 2

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

from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
q,k=map(int,input().split())
k-=1
cost=dijkstra(g,unweighted=False,directed=False)
for i in range(q):
    a,b=map(int,input().split())
    print(int(cost[a-1][k]+cost[k][b-1]))


### FIXED CODE ###

n=int(input())
ro=[{}for i in range(n)]
dis=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    ro[a-1][b-1]=c
    ro[b-1][a-1]=c
q,k=map(int,input().split())
dis[k-1]=0
stack=[k-1]
while stack:
    s=stack.pop()
    for i,j in ro[s].items():
        if dis[i] == -1:
            dis[i]=dis[s]+j
            stack.append(i)
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dis[x]+dis[y])
### BUGGY CODE ###

#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

n, k = map(int,input().split())
mod = 998244353

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    sum[i] = sum[i-1] + cnt[i]

print(cnt[-1] % mod)

### FIXED CODE ###

#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

n, k = map(int,input().split())
mod = 998244353

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] %= mod
    sum[i] = (sum[i-1] + cnt[i]) % mod

print(cnt[-1])
### BUGGY CODE ###

from collections import deque

INF = 999999999999

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
mod=10**9+7


#パスカルの三角形を使う方法.
Combi=[[] for i in range(N+1)]
Combi[0]=[1,0]

for i in range(1,N+1):
    Combi[i].append(1)
    for j in range(i):
        Combi[i].append((Combi[i-1][j]+Combi[i-1][j+1])%mod)
    Combi[i].append(0)

COMP=[2]

for i in range(1,N-1):
    if S[i]==S[i-1]:
        COMP[-1]+=1

    else:
        COMP.append(1)
L=len(COMP)

DP=[0]*(N+1)#上にある残りの個数
DP[N]=1
rest=N



for x in COMP:

    NDP=[0]*(N+1)
    for i in range(N+1):
        for j in range(i+x,N+1):
            NDP[i]+=DP[j]*Combi[j-i-1][x-1]%mod

    rest-=x
    DP=[NDP[rest-i] for i in range(N+1)]
    #print(DP,rest)
    

print(DP[0])

### FIXED CODE ###

N=int(input())
S=input()
mod=10**9+7

#DP[i]#最後においた数の右にある残っている個数
rest=N-1
DP=[1]*(N)

for s in S:
    NDP=[0]*(N)
    if s=="<":
        for i in range(rest+1):
            if i>=1:
                NDP[i-1]=(DP[i]+NDP[i-1])%mod

        DP=NDP
        for i in range(N-2,-1,-1):
            DP[i]=(DP[i+1]+DP[i])%mod

    else:
        DP=[DP[rest-i] for i in range(N)]#左右逆にして考える

        #print(DP)
        for i in range(rest+1):
            if i>=1:
                NDP[i-1]=(DP[i]+NDP[i-1])%mod

        DP=NDP
        for i in range(N-2,-1,-1):
            DP[i]=(DP[i+1]+DP[i])%mod


        DP=[DP[rest-1-i] for i in range(N)]

    rest-=1
    #print(DP,rest)

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

from itertools import product

s = input()
x, y = list(map(int, input().split()))

def adding(sign, lst):
    res = 0
    for i in range(len(sign)):
        if sign[i] == 0:
            res += lst[i]
        else:
            res -= lst[i]
    return res

a = [0, 1]

fs = s.split("T")
f_num = [len(f) for f in fs]

dir_lst = [[], []]

for i in range(len(f_num)):
    dir_lst[i%2].append(f_num[i])

x_lst = dir_lst[0]
y_lst = dir_lst[1]

aosx = product(a, repeat=len(x_lst)-1)
aosy = product(a, repeat=len(y_lst))

flag = True

for signx in aosx:
    if x_lst[0] + adding(signx, x_lst[1:]) == x:
        for signy in aosy:
            if adding(signy, y_lst) == y:
                print("Yes")
                flag = False
                break

if flag:
    print("No")

### FIXED CODE ###

from itertools import product

s = input()
x, y = list(map(int, input().split()))

a = [0, 1]

fs = s.split("T")
f_num = [len(f) for f in fs]

dir_lst = [[], []]

for i in range(len(f_num)):
    dir_lst[i%2].append(f_num[i])

x_lst = dir_lst[0].copy()
y_lst = dir_lst[1].copy()

nowx = x_lst.pop(0)
x_lst.sort()
while x_lst != []:
    if nowx > x:
        nowx -= x_lst.pop()
    else:
        nowx += x_lst.pop()

y_lst.sort()
nowy = 0
while y_lst != []:
    if nowy > y:
        nowy -= y_lst.pop()
    else:
        nowy += y_lst.pop()

if x == nowx and y == nowy:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

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

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

n = len(listStr)

dp = [[0]*13 for _ in range(len(listStr)+1)]
dp[0][0] = 1 #上から回すので、文字列の1個上の桁を0としてベースにしている

MOD = 1000000000 + 7

for i in range(n):
    if listStr[i] == "?":
        c = -1
    else:
        c = int(listStr[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki *10 + j) % 13] += dp[i][ki] #ひっ算のイメージ

    for j in range(13):
        dp[i+1][j] %= MOD
res = dp[n][5]
print(res)

### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        base = pow(10, l - i - 1, 13)

        if si == "?":
            for k in range(10):
                tmp = base * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = base * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


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

import math

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    min_ind = a.index(min(a))

    start = [min_ind - x for x in range(k) if min_ind - x >= 0]
    end = [s+k-1 for s in start]

    se = [(s, e) for s, e in zip(start, end)]
    ans = 10**6
    for s, e in se:
        ans = min(ans, math.ceil(len(a[:s])/(k-1)) + math.ceil(len(a[e+1:])/(k-1)))

    print(ans+1)

main()

### FIXED CODE ###

import math

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    min_ind = a.index(min(a))

    start = [min_ind - x for x in range(k) if min_ind - x >= 0]
    end = [s+k-1 for s in start]

    ans = 10**6
    for s, e in zip(start, end):
        ans = min(ans, math.ceil(s/(k-1)) + math.ceil((n-(e+1))/(k-1)))

    print(ans+1)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = list(map(int, input().split()))
    p = list(map(int, input().split()))
    n = N-K+1
    max = 0
    for i in range(N-K+1):
        tmp = ((sum((p[i:i+K]))+K)*0.5)
        if(max < tmp):
            max = tmp
    print('{:.12f}'.format(max))

if __name__ == '__main__':
    main()


### FIXED CODE ###

N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
p2 = [p[i]*0.5 + 0.5 for i in range(N)]
size = N + 1
cusum = [0] * size
max = 0

for i in range(N):
    cusum[i+1] = cusum[i] + p2[i]

for i in range(N-K+1):
    tmp = cusum[i+K] - cusum[i]
    if max < tmp:
        max = tmp
print(max)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j
dic2={}    

for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    (_from_,_to_) = (_in_[0],_in_[1])
    if (_from_,_to_) not in dic2:
        _sum_=0
        for j in range(int((_to_-_from_)/D)):
            _sum_ = _sum_ + int(abs(dic[_from_+j*D].real-dic[_from_+j*D+D].real)+abs(dic[_from_+j*D].imag-dic[_from_+j*D+D].imag))
        print(_sum_)
        dic2[(_from_,_to_)] = _sum_
    else:
        print(dic2[(_from_,_to_)])

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 12:24:26 2018

@author: natsukiiwano
"""
import numpy as np

_in_ = input().split(" ")
H,W,D = int(_in_[0]),int(_in_[1]),int(_in_[2])

px,py= np.zeros(90001),np.zeros(90001)
d=np.zeros(90001)
for i in range(H):
    _in_ = list(map(int,input().split(" ")))
    for j in range(W):
        px[_in_[j]]=i
        py[_in_[j]]=j

for i in range(D+1,H*W+1):
    d[i]=d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())
for i in range(Q):
    _in_ = input().split(" ")
    L,R = int(_in_[0]),int(_in_[1])
    print(int(d[R]-d[L]))
### BUGGY CODE ###

def II(): return int(input())
def LI(): return [int(i) for i in input().split()]

N, K = LI()
H = LI()

cost = [0] * N
cost[0] = 0
for n in range(1, N):
  MIN = min(
  	[ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, K+1) if n-k>=0 ]
  )
  cost[n] = MIN

print(cost[-1])

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
bridges = set()
ms2 = sorted((tuple(map(int, input().split())) for i in range(m)), key=operator.itemgetter(1))

for i in range(m):
    if any(x in bridges for x in range(ms2[i][0], ms2[i][1])):
        pass
    else:
        bridges.add(ms2[i][1]-1)

if __name__ == "__main__":
    print(len(bridges))


### FIXED CODE ###

# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
bridges = [0]
ms = sorted((tuple(map(int, input().split())) for i in range(m)), key=operator.itemgetter(1))

for i in range(m):
    if ms[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)
### BUGGY CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        dp[(x-1) + i] += 1
        i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        if dp[(x-1)] == 2:
            break
        else:
            dp[(x-1) + i] += 1
            i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

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

N=int(input())
a=[-1]*(N+1)
for i in range(1,N+1):
  a[i]=int(input())
pos = 1
prev=[1]  
for _ in range(N):
  if pos == 2:
    print(len(prev)-1)
    exit(0)
  pos = a[pos]
  if pos not in prev:
    prev.append(pos)
  

print(- 1)

### FIXED CODE ###

N=int(input())
a=[-1]*(N+1)
for i in range(1,N+1):
  a[i]=int(input())
pos = 1
ans = 0
for _ in range(N):
  if pos == 2:
    print(ans)
    exit(0)
  pos = a[pos]
  ans += 1
  

print(- 1)
### BUGGY CODE ###

import itertools
n = int(input())
s = [int(i) for i in input()]
a = set(itertools.combinations(s, 3))

print(len(a))


### FIXED CODE ###

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

l = [str(i).zfill(3) for i in range(0,1000)]

ct = 0
for i in l:
  n0 = s.find(i[0])
  if n0==-1:
    continue
  n1 = s.find(i[1], n0+1)
  if n1==-1:
    continue
  n2 = s.find(i[2], n1+1)
  if n2!=-1:
    ct += 1
   
print(ct)
### BUGGY CODE ###

def maximum_profit(n):
    maxv = min(n) - max(n)
    for i in range(len(n)-1):
        m = max(n[i+1:])
        if maxv < m - n[i]:
            maxv = m - n[i]
    return maxv

if __name__ == '__main__':
    n = []
    for _ in range(int(input())):
        n.append(int(input()))
    print(maximum_profit(n))



### FIXED CODE ###

def maximum_profit(n):
    maxv = min(n) - max(n)
    minv = n[0]
    for i in range(1, len(n)):
        maxv = n[i] - minv if maxv < n[i] - minv else maxv
        minv = n[i]        if minv > n[i]        else minv
    return maxv
if __name__ == '__main__':
    n = int(input())
    numbers = [int(input()) for i in range(0, n)]
    print(maximum_profit(numbers))
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

#最も大きなunionの大きさが答え
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

AB = []
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    unite(a,b)

ans = 0
for i,j in all_group_members().items():
    ans = max(ans,len(j))
print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

#最も大きなunionの大きさが答え
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

AB = []
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    unite(a,b)

ans = 0
for i in par:
    if i < 0:
        ans = max(ans,-i)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
else:
    count = 1
    flag = True
    for i in range(N):
        count = count * A[i]
        if count > 10 ** 18:
            print(-1)
            flag = False
            break
    if flag:
        print(count)
### BUGGY CODE ###

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i in r :
    for j in range(i+1,N):
        for k in r:
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()