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

from heapq import heappush, heappop, heapify
import math
def solve():
	n , k= map(int, input().strip().split())
	# if k >= 10*8:
	# 	return 1
	a= [(-int(x),1,int(x)) for x in input().strip().split()]
	heapify(a)
	for i in range(k):
		x,cnt,orig = heappop(a)
		heappush(a,(-((orig+cnt)//(cnt+1)),cnt+1,orig))
	return -(heappop(a)[0])
 
 
print(solve())

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math
def check(a,mid,k):
	cnt = 0
	for x in a:
		cur_cnt = (x+mid-1)//mid - 1
		cnt+=cur_cnt
		if cnt > k:
			return False
	return True

def solve():
	n , k= map(int, input().strip().split())
	a= [int(x) for x in input().strip().split()]
	l = 0
	r = 10**9+20
	while r-l > 1:
		mid = (r+l)//2
		if check(a,mid,k):
			r = mid
		else:
			l = mid
	return l+1
 
print(solve())
### BUGGY CODE ###

N = int(input())
AList = list(map(int, input().split()))

count = 0
roop = 0
while True:
	for i in range(N):
		AList[i] = AList[i] / 2
		if AList[i] % 2 == 0:
			break
		count += 1
roop = count // N
print(roop)

### FIXED CODE ###

N = int(input())
Alist = list(map(int, input().split()))

flag = True
count = 0
while flag:
	for i in range(N):
		if Alist[i] % 2 != 0:
			flag = False
			break

	if flag:
		for i in range(N):
			Alist[i] = Alist[i] / 2
		count += 1

print(count)
### BUGGY CODE ###

import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
    buf.append(ans)
print('\n'.join(map(str, buf)))


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

n, k = map(int,input().split())
a = input().split()
ls = []
times = 1

for j in range(0,(n-k)+1):
    for i in range(j,j+k):
        times *= int(a[i])
    ls.append(times)
    times = 1

for x in range(len(ls)-1):
    if ls[x] < ls[x+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
    if a[i] < a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def dw_heap(A,i,length):
    l = i*2
    r = i*2 + 1
    largest = i
    if l < length and A[l] > A[largest]: largest = l
    if r < length and A[r] > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest, length)


def up_heap(A,i):
    if i==1: return
    p = i//2
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def extract(A,last):
    max_item = A[1]
    A[1],A[last] = A[last],A[1]
    dw_heap(A,1,last)
    return max_item


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*2*10**6
    i = 1
    while True:
        op = input().split() 
        if   op[0] != 'insert': break
        hp[i] = int(op[1])
        i += 1
    if op[0] != 'end': build_heap(hp,i)
    while True:
        if   op[0] == 'end': break
        if   op[0] == 'insert':
            hp[i] = int(op[1])
            up_heap(hp,i)
            i += 1
        else:
            print(extract(hp,i-1))
            i -= 1
        op = input().split() 

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')
### BUGGY CODE ###

N, M = map(int, input().split())
L = [list(input().split()) for i in range(M)]
ac = [L[j][0] for j in range(M) if L[j][1] == 'AC']
AC = list(set(ac))
P = 0
for k in AC:
  n = L.index([k, 'AC'])
  P += L[:n].count([k, 'WA'])
print(len(AC), P)

### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * (N + 1)
S = [0] * (N + 1)
for i in range(M):
  x, p = input().split()
  s = int(x)
  if P[s] == 0:
    if p == 'AC':
      P[s] = 1
    else:
      S[s] += 1
A = sum([S[i] for i in range(N + 1) if P[i] == 1])
print(P.count(1), A)
### BUGGY CODE ###

import itertools

line = str(input())
lines = line.split(' ')

n = int(lines[0])
k = int(lines[1])

d = list()

line = str(input())
lines = line.split(' ')

for l in lines:
    d.append(int(l))

ds = list()

for i in range(0,n):
    for len in range(1,n-i+1):
        sum = 0
        for j in range(i,i+len):
            sum += d[j]
        ds.append(sum)

digit = 0
o = list()

for i in range(31,-1,-1):
    count = 0
    o.clear()
    for dss in ds:
        if dss & (1 << i) > 0 :
            count += 1
            o.append(dss)
    if count >= k :
        digit = i
        break

ls = list(itertools.combinations(o,k))

max = 0
for t in ls:
    sum = t[0]

    for u in t:
        sum = sum & u

    if sum > max : 
        max = sum

print(max)

### FIXED CODE ###

n,k=map(int,input().split())
d=list(map(int,input().split()))

ds = []

for i in range(0,n):
    sum = 0
    for j in range(i,n):
        sum += d[j]
        ds.append(sum)
        #print(str(sum) + " ",end='')
    #print()

ds.sort(reverse=True)

sum = 0
for i in range(40,-1,-1):
    count = 0
    o = []
    for dss in ds:
        if dss & (1 << i) > 0 :
            count += 1
            o.append(dss)

    if count >= k :
        sum += 1 << i
        ds = o

print(sum)
### BUGGY CODE ###

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

### FIXED CODE ###

d = 1000000007
n = int(input())
a = list(map(int, input().split()))
summation = sum(a)
diagonal = 0
for i in range(len(a)):
        diagonal += a[i] ** 2 
ans = (((summation  ** 2) - diagonal) // 2) % d
print(ans)
### BUGGY CODE ###

(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
            cGT.append(e[1])
        elif e[1] in c:
            aru = True
            c.append(e[0])
            cGT.append(e[0])
    if not aru:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
res = 0
for i in list(set(p) - cGT):
    if p[i - 1] == i:
        res = res + 1

for i in cGT:
    for c in cG:
        if i in c:
            if p.index(i) + 1 in c:
                res = res + 1
                break
print(res)


### FIXED CODE ###

def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


def sameroot(x, y):
    return root(x) == root(y)


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)
### BUGGY CODE ###

N = int(input())

cnt = 0
S_list = [list(input()) for _ in range(N)]
S_symmetry = [['' for _ in range(N)] for _ in range(N)]


def count_symmetry():
    for i in range(N):
        for j in range(N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    for i in range(N):
        for j in range(N):
            S_symmetry[i][(j + k) % N] = S_list[i][j]
    if count_symmetry():
        cnt += 1

print(cnt * N)


### FIXED CODE ###

N = int(input())
S_list = [input() for _ in range(N)]
cnt = 0


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(i + 1, N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

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

H, W = map(int,input().split())

A = [[False for _ in range(W)] for _ in range(H)]

Q = []
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while Q:
    ans += 1
    NQ = []
    for y, x in Q:
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

A, B, Q = map(int,input().split())

ss = [-10**10]+[int(input()) for _ in range(A)]+[2*10**10]
ts = [-10**10]+[int(input()) for _ in range(B)]+[2*10**10]
xs = [int(input()) for _ in range(Q)]

def binarysearch(ls,x):
    n = len(ls)
    width = n//2
    pos = n//2
    while True:
        width = (width+1)//2
        if ls[pos] < x < ls[pos+1]:
            index = pos
            break    
        elif x < ls[pos]:
            pos -= width
        elif ls[pos+1] < x:
            pos += width
        pos = min(n-1,pos)
        pos = max(pos,0)
    return index

for x in xs:
    sind = binarysearch(ss,x)
    tind = binarysearch(ts,x)
    
    s0,s1,t0,t1 = ss[sind],ss[sind+1],ts[tind],ts[tind+1]
    d1,d2,d3,d4 = 10**10,10**10,10**10,10**10

    d1 = max(x-s0,x-t0)
    d2 = min((t1-x)*2+(x-s0),(x-s0)*2+(t1-x))
    d3 = min((s1-x)*2+(x-t0),(x-t0)*2+(s1-x))
    d4 = max(s1-x, t1-x)
    print(min(d1,d2,d3,d4))

### FIXED CODE ###

from bisect import bisect_right as binarysearch
A, B, Q = map(int,input().split())

ss = [-10**10]+[int(input()) for _ in range(A)]+[2*10**10]
ts = [-10**10]+[int(input()) for _ in range(B)]+[2*10**10]
xs = [int(input()) for _ in range(Q)]
for x in xs:
    sind = binarysearch(ss,x)-1
    tind = binarysearch(ts,x)-1
    
    s0,s1,t0,t1 = ss[sind],ss[sind+1],ts[tind],ts[tind+1]
    d1,d2,d3,d4 = 10**10,10**10,10**10,10**10

    d1 = max(x-s0,x-t0)
    d2 = min((t1-x)*2+(x-s0),(x-s0)*2+(t1-x))
    d3 = min((s1-x)*2+(x-t0),(x-t0)*2+(s1-x))
    d4 = max(s1-x, t1-x)
    print(min(d1,d2,d3,d4))
### BUGGY CODE ###

N, Q = map(int, input().rstrip().split())
S = input()

count = [0 for i in range(len(S))]

list_lr = [map(int, input().rstrip().split()) for i in range(Q)]

for i in list_lr:
    l, r = i
    s = S[l-1:r]

    print(s.count('AC'))


### FIXED CODE ###

N, Q = map(int, input().rstrip().split())
S = [i for i in input()]

list_lr = [list(map(int, input().rstrip().split())) for i in range(Q)]

t = [0]
ct = 0
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ct += 1
    t.append(ct)

for i in list_lr:
    l, r = i[0], i[1]
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)

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

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

DP1 = [-1] * (N + 1)
DP1[0] = 1
parent = [-1] * (N + 1)
parent[1] = 0

def dfs(x, p):
    tmp = 1
    for next_ in G[x]:
        if next_ == p:
            continue
        parent[next_] = x
        tmp *= (dfs(next_, x) + 1)
        # tmp %= MOD
    DP1[x] = tmp
    return tmp

dfs(1, 0)
# print (DP1)

DP2 = [-1] * (N + 1)
DP2[0] = 1
DP2[1] = 1
stack = [1]

while stack:
    x = stack.pop()
    for next_ in G[x]:
        if DP2[next_] != -1:
            continue
        tmp = DP1[x]
        tmp //= (DP1[next_] + 1)
        tmp *= DP2[parent[next_]]
        tmp += 1 #白色の分
        DP2[next_] = tmp
        stack.append(next_)

# print (DP2)

for i in range(1, N + 1):
    print (DP1[i] * DP2[i] % MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)

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


G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
G[0].append(1)
G[1].append(0)

DP1 = [0] * (N + 1)

parent = [-1] * (N + 1)
parent[1] = 0

order = []

stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for next_ in G[x]:
        if next_ == parent[x]:
            continue
        parent[next_] = x
        stack.append(next_)

for v in order[::-1]:
    tmp = 1
    for next_ in G[v]:
        tmp *= DP1[next_] + 1
        tmp %= MOD
    DP1[v] = tmp
# print (DP1)

DP2 = [1] * (N + 1)

for x in order:
    # 累積積のパート
    #ここが同じ値を返すかチェックする
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        #親のときだけは違うルールで対処
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == parent[x]:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 #白色の分
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])

# print (DP2)

for i in range(1, N + 1):
    print ((DP1[i] * DP2[i]) % MOD)

# print (DP1)
# print (DP2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

def f(x):
    if x == 0:
        return True
    elif x < 0:
        return False
    for i in range(6):
        if f(x-100-i):
            return True
    return False

def main():
    X = int(input())
    print(int(f(X)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

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

from collections import deque, Counter
import itertools

H, W, M = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(M)]

F = [[0 for _ in range(W + 1)] for _ in range(H + 1)]

d_h = deque()
d_w = deque()
for h, w in HW:
    d_h.append(h)
    d_w.append(w)
    F[h][w] += 1

# 出現頻度順にソート
c_h = Counter(d_h).most_common()
c_w = Counter(d_w).most_common()

# 登場頻度の一番高い回数
n_h = c_h[0][1]
n_w = c_w[0][1]

# 同率のものを数える
t_h = deque()
t_w = deque()

for k, v in c_h:
    if v == n_h:
        t_h.append(k)
    else:
        break

for k, v in c_w:
    if v == n_w:
        t_w.append(k)
    else:
        break

q = set(list(itertools.product(t_h, t_w)))

for h, w in HW:
    q.discard((h, w))

if len(q) == 0:
    ans = n_h + n_w - 1
else:
    ans = n_h + n_w

print(ans)


### FIXED CODE ###

import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
if A+B-1>N or N>A*B:
    print(-1)
else:
    blocks = [[] for _ in range(A)]
    cnt = N
    blocks[0] = list(range(B, 0, -1))
    flg = True
    while flg:
        flg = False
        for i in range(A-1, 0, -1):
            blocks[i].append(cnt)
            cnt -= 1
            if cnt==B:
                break
        else:
            flg = True
    ans = [0]*N
    cnt = 0
    for b in blocks:
        for a in b:
            ans[cnt] = a
            cnt += 1
    print(*ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
from collections import deque
if A+B-1>N or N>A*B:
    print(-1)
else:
    blocks = []
    blocks.append(' '.join(map(str, range(B, 0, -1))))
    now = B+1
    rest = N-A+2

    while now:
        if now>=rest:
            break
        if now+B>rest:
            blocks.append(' '.join(map(str, range(rest, now-1, -1))))
            rest += 1
            break
        blocks.append(' '.join(map(str, range(now+B-1, now-1, -1))))
        now = now+B
        rest += 1
    blocks.append(' '.join(map(str, range(rest, N+1))))
    print(' '.join(blocks))
### BUGGY CODE ###

N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-1):
    if not Possible:
        break
    for j in range(i+1, N):
        if not Possible:
            break
        for k in range(N):
            if not Possible:
                break
            if A[i][j] <= A[i][k]+A[j][k]:
                if k != i and k !=j:
                    if A[i][j] == A[i][k]+A[j][k]:
                        NoNeed |= {(i, j)}
            else:
                Possible = False        

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    for a in NoNeed:
        Total -= A[a[0]][a[1]]
    print(Total)
else:
    print(-1)

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()