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

num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_count = 0
    s_limit = int(i ** 0.5)
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j > k:
                        if k > l:
                            xyz_count += 6
                        else:
                            xyz_count += 3
                    elif k == l:
                        xyz_count += 1
                    else:
                        xyz_count += 3
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0]*n
b=[0]*m
c=[0]*m
a=list(map(int,input().split()))
for i in range(m):
  b[i],c[i]=map(int,input().split())
  for j in range(b[i]):
    a.append(c[i])
    
a=sorted(a,reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*n
List={}
a=list(map(int,input().split()))
for i in range(n):
  List.setdefault(a[i],0)
  List[a[i]]+=1
ans=0

for i in range(m):
  b,c=map(int,input().split())
  List.setdefault(c,0)
  List[c]+=b
  
List_sorted=sorted(List, reverse=True)

#print(List)
#print(List_sorted)
for i in List_sorted:
  if (List[i]<n):
    ans+=i*List[i]
    n-=List[i]
  else:
    ans+=i*n
    break
    
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    N,C = map(int, input().split())
    X = []
    for _ in range(N):
        X.append(list(map(int, input().split())))
    
    cw = [0] # 時計回りに数えて i 番目までを食べた時に摂取できるカロリー
    ccw = [0] # 反時計回り
    for i in range(N):
        cw.append(cw[i] + X[i][1])
        ccw.append(ccw[i] + X[N-1-i][1])
    for i in range(N):
        cw[i+1] -= X[i][0]
        ccw[i+1] -= C - X[N-1-i][0]
    ans = 0
    # i 番目で向きを変えて、j 番目まで食べる場合を全探索
    # O(n^2) なのでアカンか…？
    for i in range(N+1):
        cwccw = cw[i]
        ccwcw = ccw[i]
        if i > 0:
            cwccw -= X[i-1][0] # 原点に戻るコスト
            ccwcw -= C - X[N-i][0]
        for j in range(N+1-i):
            ans = max(ans, cwccw + ccw[j])
            ans = max(ans, ccwcw + cw[j])

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N,C = map(int, input().split())
    X = []
    for _ in range(N):
        X.append(list(map(int, input().split())))
    
    cw = [0] # 時計回りに数えて i 番目までを食べた時に摂取できるカロリー
    ccw = [0] # 反時計回り
    for i in range(N):
        cw.append(cw[i] + X[i][1])
        ccw.append(ccw[i] + X[N-1-i][1])
    for i in range(N):
        cw[i+1] -= X[i][0]
        ccw[i+1] -= C - X[N-1-i][0]

    ma = 0
    ga = []
    for i in range(0, N+1):
        ma = max(ma, cw[i])
        ga.append(ma)
    ma = 0
    gb = []
    for i in range(0, N+1):
        ma = max(ma, ccw[i])
        gb.append(ma)

    ans = 0
    for bi in range(N+1):
        tmp = ccw[bi] + ga[N-bi]
        if bi > 0:
            tmp -= C - X[N-bi][0]
        ans = max(ans, tmp)

    for ai in range(N+1):
        tmp = cw[ai] + gb[N-ai]
        if ai > 0:
            tmp -= X[ai-1][0]
        ans = max(ans, tmp)

    print(ans)

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

N = int(input())

A = list(map(int, input().split()))
sum=1
for n in A:
    sum=sum*n

if sum>10**18:
    sum = -1

print(sum)

### FIXED CODE ###


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

if 0 in A:
    print(0)
else:
    for n in range(N):
        sum = sum * A[n]
        if sum>1000000000000000000:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

import sys
import array

from operator import itemgetter

input = sys.stdin.readline

tl=200100

ft=array.array('I', [0 for _ in range(tl)])

def upd(i):
	global ft
	i+=1
	while(i<tl):
		ft[i]+=1
		i+=i&-i

def get(i):
	global ft
	i+=1
	ret=0
	while(i!=0):
	    ret+=ft[i]
	    i-=i&-i
	return ret

md = 998244353
n = int(input())

xyi = [[0]*3 for _ in range(n)]
for i in range(n):
	xyi[i][0],xyi[i][1] = [int(item) for item in input().split()]
xyi.sort(key=itemgetter(0))

for i in range(n):
	xyi[i][2]=i
xyi.sort(key=itemgetter(1))

ct=[0]*(n+1)

ct[0]=1
for i in range(1,n+1):
	ct[i]=ct[i-1]*2%md

cnt=tuple(ct)

def comb(x):
	return cnt[x]-1;

ans=0

for aa in xyi:
	ix=aa[2]
	a=get(ix)
	b=get(n)-a
	c=ix-a
	d=n-ix-1-b
#	exc=(comb(a+b)+comb(a+c)+comb(b+d)+comb(c+d)-comb(a)-comb(b)-comb(c)-comb(d))%md
#	cur=(comb(n)-exc)%md
#	ans=(ans+cur)%md
	ans=(ans+comb(n)-comb(a+b)-comb(a+c)-comb(b+d)-comb(c+d)+comb(a)+comb(b)+comb(c)+comb(d))%md
	upd(ix)

if(ans<0):ans+=md

print(ans)


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
que = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(que) > 0:
    cur, cost, _from = que.pop(0)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        que.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))

### FIXED CODE ###

import sys

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
### BUGGY CODE ###

import numpy as np
N = int(input())
aaa = np.array(list(map(int, input().split())), dtype='int64')
MOD = 1_000_000_007
ans = 0
for j in range(1, N):
    ans += sum((aaa[:j] ^ aaa[j]) % MOD)
    ans %= MOD
print(ans)


### FIXED CODE ###

N = int(input())
aaa = list(map(int, input().split()))
bbb = [format(a, '061b') for a in aaa]

zero = [0] * 61
one = [0] * 61
for i in range(61):
    s = ''.join(list(b[-(i+1)] for b in bbb))
    zero[i] = s.count('0')
    one[i] = s.count('1')
ans = 0
MOD = 1_000_000_007
for i, o, l in zip(range(61), zero, one):
    ans += 2**i * o * l
    ans %= MOD
print(ans)
### BUGGY CODE ###

import heapq

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AA = list(map(lambda x:x*(-1), A))
    BB = list(map(lambda x:x*(-1), B))
    CC = list(map(lambda x:x*(-1), C))

    ans = []
    heapq.heapify(ans)
    for a in AA:
        for b in BB:
            for c in CC:
                heapq.heappush(ans, a+b+c)
    
    for i in range(K):
        print(heapq.heappop(ans)*(-1))
main()

### FIXED CODE ###

from heapq import heappush, heapify, heappop

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    
    que = []
    heapify(que)
    heappush(que, (-A[0]-B[0]-C[0], 0, 0, 0))
    s = set()
    
    for i in range(K):
        ans = heappop(que)
        print(-ans[0])
        if(ans[1] < X-1 and not (ans[1]+1, ans[2], ans[3]) in s):
            heappush(que, [-A[ans[1]+1]-B[ans[2]]-C[ans[3]], ans[1]+1, ans[2], ans[3]])
            s.add((ans[1]+1, ans[2], ans[3]))
        if(ans[2] < Y-1 and not (ans[1], ans[2]+1, ans[3]) in s):
            heappush(que, [-A[ans[1]]-B[ans[2]+1]-C[ans[3]], ans[1], ans[2]+1, ans[3]])
            s.add((ans[1], ans[2]+1, ans[3]))
        if(ans[3] < Z-1 and not (ans[1], ans[2], ans[3]+1) in s):
            heappush(que, [-A[ans[1]]-B[ans[2]]-C[ans[3]+1], ans[1], ans[2], ans[3]+1])
            s.add((ans[1], ans[2], ans[3]+1))   
main()
### BUGGY CODE ###

from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
monster = deque(monster)
final = monster[-1][0]
ruiseki = 0
minuslist = deque()

while len(monster) > 0:
  while len(minuslist) > 0:
    if monster[0][0] >= minuslist[0][0]:
      ruiseki -= minuslist.popleft()[1]
    else:
      break
  if ruiseki < monster[0][1]:
    ans += monster[0][1] - ruiseki
    if monster[0][0] + 2*D +1 <= final:
      minuslist.append([monster[0][0]+2*D+1, monster[0][1] - ruiseki])
    ruiseki = monster.popleft()[1]

print(ans)


### FIXED CODE ###

N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
"""
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = monster[k][1]
    ans += monster[k][1]
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk
"""
final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


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

for e in iter(input,'-1'):
 q=float(input())
 x=q/2
 while abs(x**3-q)>=q*1e-5:x-=(x**3-q)/(3*x*x)
 print(x)


### FIXED CODE ###

for e in iter(input,'-1'):
 q=float(e)
 x=q/2
 while abs(x**3-q)>=q*1e-5:x-=(x**3-q)/3/x/x
 print(x)
### BUGGY CODE ###

N ,P= map(int,input().split())
S = input()
if P != 2 and P != 5:
    mod_dic ={}
    mod_dic[0] = 1
    for i in range(len(S)):
        num  = int(S[len(S)-i-1:])
        mod = num%P
        if mod not in mod_dic:
            mod_dic[mod] = 1
        else:
            mod_dic[mod] += 1
        ans = 0
    a = list(mod_dic.values())
    for i in range(len(a)):
            ans += a[i] * (a[i]-1) //2
    print(ans)
elif P == 2:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%2 == 0:
            ans += N-i
    print(ans)
else:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%5 == 0:
            ans += N-i
    print(ans)

### FIXED CODE ###

N ,P= map(int,input().split())
S = input()
ten = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        ten[i] = 1
    else:
        ten[i] = (ten[i-1] * 10) %P
if P != 2 and P != 5:
    mod_dic ={}
    mod_dic[0] = 1
    mod = 0
    for i in range(len(S)):
        mod +=  int(S[N-1-i]) * ten[i]
        mod = mod%P
        if mod not in mod_dic:
            mod_dic[mod] = 1
        else:
            mod_dic[mod] += 1
        ans = 0
    a = list(mod_dic.values())
    for i in range(len(a)):
            ans += a[i] * (a[i]-1) //2
    print(ans)
elif P == 2:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%2 == 0:
            ans += N-i
    print(ans)
else:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%5 == 0:
            ans += N-i
    print(ans)
### BUGGY CODE ###

import numpy as np
import math
"""
def search(min_,max_,A,B,arr):
#    print(min_,max_)
    if min_==max_:
        return min_
    mid=(max_+min_)//2
    
    tmp=arr-mid*B
    
    if len(tmp)==0:
        return search(min_,mid,A,B,arr)
    
    tmp=map(lambda x:math.ceil(x/(A-B)),tmp)
    sum_=sum(list(tmp))
    if sum_<=mid:
        return search(min_,mid,A,B,arr)
    else:
        return search(mid+1,max_,A,B,arr)

    while True:
        if k<0:
            if mid==min_:
                return max_
            else:
                #failure
                return search(mid,max_,A,B,arr[:L])
        elif len(tmp)==0:
            #success
            return search(min_,mid,A,B,arr)
        x=-tmp[0]
        tmp=np.delete(tmp,0)
        k-=x//(A-B)+(x%(A-B)>0)
"""
        
    
N,A,B=list(map(int,input().split()))
arr=[]

for i in range(N):
    h=int(input())
    arr.append(h)
arr=np.array(arr)

max_=max(arr)//B+1
min_=min(arr)//A

d=A-B

while min_!=max_:
    mid=(max_+min_)//2
    
    tmp=arr-mid*B
    tmp=map(lambda x:math.ceil(x/d),tmp)
    sum_=sum(list(tmp))
    
    if sum_<=mid:
        max_=mid
    else:
        min_=mid+1

print(min_)

### FIXED CODE ###

import math
"""
def search(min_,max_,A,B,arr):
#    print(min_,max_)
    if min_==max_:
        return min_
    mid=(max_+min_)//2
    
    tmp=arr-mid*B
    
    if len(tmp)==0:
        return search(min_,mid,A,B,arr)
    
    tmp=map(lambda x:math.ceil(x/(A-B)),tmp)
    sum_=sum(list(tmp))
    if sum_<=mid:
        return search(min_,mid,A,B,arr)
    else:
        return search(mid+1,max_,A,B,arr)

    while True:
        if k<0:
            if mid==min_:
                return max_
            else:
                #failure
                return search(mid,max_,A,B,arr[:L])
        elif len(tmp)==0:
            #success
            return search(min_,mid,A,B,arr)
        x=-tmp[0]
        tmp=np.delete(tmp,0)
        k-=x//(A-B)+(x%(A-B)>0)
"""
        
    
N,A,B=list(map(int,input().split()))
arr=[]

for i in range(N):
    arr.append(int(input()))

max_=max(arr)//B+1
min_=min(arr)//A

d=A-B

while min_!=max_:
    mid=(max_+min_)//2
    
    sum_=0
    for x in arr:
        sum_+=max(0,math.ceil((x-mid*B)/d))
        
    if sum_<=mid:
        max_=mid
    else:
        min_=mid+1

print(min_)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val *= 2

print(*ans, sep = "\n")

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val0to1 = 1
val1to0 = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val0to1 % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val1to0 % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val0to1 = val0to1 * 2 % (count1 + 1)
  if count1 != 1:
    val1to0 = val1to0 * 2 % (count1 - 1)

print(*ans, sep = "\n")
### BUGGY CODE ###

import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=sum(bit)
    ans+=s*(n-s)*po
    ans%=N
    po*=2
    po%=N
print(ans)


### FIXED CODE ###

import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=np.count_nonzero(bit)
    ans+=s*(n-s)%N*po
    ans%=N
    po*=2
    po%=N
print(ans)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    dp[i] = min([dp[j] + abs(h[j] - h[i]) for j in range(max(0, i - k), i)])
print(dp[-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
edges = deque(edges)
ans = 0
while edges:
    d, u, v = edges.popleft()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)


### FIXED CODE ###

from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)
### BUGGY CODE ###

NK = [int(i) for i in input().split(" ")]
list1 = [(int(i)+1)/2 for i in input().split(" ")]
Max = 0
for j in range(NK[0]-NK[1]+1):
    if Max<sum(list1[j:j+NK[1]]):
        Max=sum(list1[j:j+NK[1]])
print(Max)

### FIXED CODE ###

Input1 = [int(_) for _ in input().split(" ")]
Input2 = [(int(i)+1)/2 for i in input().split(" ")]

sum_ = sum(Input2[:Input1[1]])
Max = sum_
for j in range(Input1[0]-Input1[1]):
    sum_ = sum_-Input2[j]+Input2[j+Input1[1]]
    if Max  < sum_:
        Max = sum_
        
print(Max)
### BUGGY CODE ###


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

def addEdge(graph,u,v):
    graph[u].append(v)


def adjAB(graph,node):
    Aflag =False
    Bflag =False
    for i in graph[node]:
        if s[i-1]=='A':
            Aflag = True
        if s[i-1]=='B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)


def deleteNode(graph,node):
    graph.pop(node,None)
    for i in graph:
        while node in graph[i]:
            graph[i].remove(node)


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    if i != j:
        addEdge(graphAB,j,i)


flag = True

while flag:
    flag = False
    deletelist = []
    for i in graphAB:
        if not adjAB(graphAB,i):
            deletelist.append(i)
            flag = True
    for i in deletelist:
        deleteNode(graphAB,i)


if graphAB == {}:
    print('No')
else:
    print('Yes')




### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')