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

# -*- coding:utf-8 -*-
import copy

INF = 2*(10**8)+1
memo = INF  # メモ化用変数

def solve():
    N, K = list(map(int, input().split(" ")))
    X = [0]
    X.extend(list(map(int, input().split(" "))))
    X.sort()


    def dfs(depth, cost, i, Xs):
        global memo
        if depth == K:
            memo = min(cost, memo)
            return cost
        
        if cost >= memo:
            # 探索を打ち切る
            return INF
        
        ret1, ret2 = INF, INF
        if i+1 < len(Xs):
            # 右に移動
            tmpCost = abs(Xs[i] - Xs[i+1])
            tmpXs = copy.deepcopy(Xs)
            del tmpXs[i]
            ret1 = dfs(depth+1, cost+tmpCost, i, tmpXs)
        if i-1 >= 0:
            # 左に移動
            tmpCost = abs(Xs[i] - Xs[i-1])
            tmpXs = copy.deepcopy(Xs)
            del tmpXs[i]
            ret2 = dfs(depth+1, cost+tmpCost, i-1, tmpXs)
        
        return min(ret1, ret2)

    # 0座標のインデックスは？
    for i in range(len(X)):
        if X[i] == 0:
            break
    ans = dfs(0, 0, i, X)
    print(ans)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

# -*- coding:utf-8 -*-

"""解説
https://www.youtube.com/watch?v=5O4k1n5Ejzw

区間を考える問題

-30 -10 0 10 20 50

・K = 3のとき、

0座標を必ず含める、ある連続するK個のロウソクについて考える

・-30 -10 0 10
・-10 0 10 20
・0 10 20 50

左端と右端に到達する最小値を求めていけばよくて、間のロウソクは無視してよい（必ず移動中に火をつけるので）

すべての場合について求めて、その中の最小値が答え
"""
def solve():
    N, K = list(map(int, input().split()))
    X = list(map(int, input().split()))
    if 0 in X:
        # 0座標にロウソクがあるなら、火をつけるロウソクをひとつ減らしてよい
        K -= 1
    else:
        X.append(0)
    X.sort()

    origin_i = X.index(0)
    left_i = max(origin_i-K, 0)

    INF = 10**12
    ans = INF
    while left_i <= origin_i:
        if left_i+K < len(X):
            tmp1 = abs(X[left_i]-0)*2 + abs(X[left_i+K]-0)
            tmp2 = abs(X[left_i]-0) + abs(X[left_i+K]-0)*2
        else:
            break
        ans = min(ans, tmp1, tmp2)
        left_i += 1
    print(ans)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    def ask(n):
        print(n)
        sys.stdout.flush()
        s = input().rstrip('\n')
        if s == 'Vacant':
            exit()
        elif s == 'Male':
            return 0
        else:
            return 1

    N = int(input())

    a0 = ask(0)
    ok = 0
    ng = N-1
    mid = (ok+ng)//2
    while ng - ok > 1:
        a = ask(mid)
        if a == a0:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    _ = ask(N-1)
    assert False


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    def ask(n):
        print(n)
        sys.stdout.flush()
        s = input().rstrip('\n')
        if s == 'Vacant':
            exit()
        elif s == 'Male':
            return 0
        else:
            return 1

    N = int(input())

    a0 = ask(0)
    ok = 0
    ng = N-1
    mid = ((ng//2)//2) * 2
    while ng - ok > 2:
        a = ask(mid)
        if a == a0:
            ok = mid
        else:
            ng = mid
        mid = (((ok//2)+(ng//2))//2)*2
    ask((ok+ng)//2)
    ask(N-1)


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

def gcd(p, q):
    if p % q == 0:
        return q
    return gcd(q, p % q)


N = int(input())

ans = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        for c in range(1, N + 1):
            ans += gcd(gcd(a, b), c)

print(ans)


### FIXED CODE ###

from math import gcd

N = int(input())

ans = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        for c in range(1, N + 1):
            ans += gcd(gcd(a, b), c)

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

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    s = list(input())
    q = int(input())
    reverse = False
    
    for _ in range(q):
        query = list(input().split())
        if query[0] == '1':
            if reverse:
                reverse = False
            else:
                reverse = True
        else:
            if reverse:
                if query[1] == '1':
                    s = s + [query[2]]
                else:
                    s = [query[2]] + s
            else:
                if query[1] == '1':
                    s = [query[2]] + s
                else:
                    s = s + [query[2]]
                    
    s = ''.join(s)
    if reverse:
        print(s[::-1])
    else:
        print(s)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

def main():
    s = deque(input())
    q = int(input())
    reverse = False
    
    for _ in range(q):
        query = list(input().split())
        if query[0] == '1':
            reverse ^= True
        else:
            if reverse:
                if query[1] == '1':
                    s.append(query[2])
                else:
                    s.appendleft(query[2])
            else:
                if query[1] == '1':
                    s.appendleft(query[2])
                else:
                    s.append(query[2])
                    
    s = ''.join(s)
    if reverse:
        s = s[::-1]
    print(s)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))
I = list()
J = list()
ans = 0

for i in range(N):
  I.append(A[i]+i)
  J.append(i-A[i])
for i in I:
  ans += J.count(i)
    
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
from collections import defaultdict
I = defaultdict(int)
J = defaultdict(int)
ans = 0

for i in range(N):
  I[A[i]+i] += 1
  J[i-A[i]] += 1
for i,j in I.items():
  ans += J[i]*j
    
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[None]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=None:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS=(ANS+dp(NOW+2**i,x+1))%mod

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+(1<<i),x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))
### BUGGY CODE ###

from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
for i in range(len(S)):
    q = (t[-1] + int(S[i]) * (10**i)) % MOD
    t.append(q)

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

### FIXED CODE ###

from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r) % MOD) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3


def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()


### FIXED CODE ###

def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


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

import numpy as np
n,w=map(int,input().split())
#重さをdpにする
#dp=[[0]*n,[0]*w] #n番目の品,重さ。価値が値として入る
dp=np.zeros((n+1,w+1))

W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W+=[a]
    V+=[b]

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_w in range(w+1):
        #print(sum_w)
        #足した時に価値が上がるケース
        if sum_w>=W[i]:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - W[i]] + V[i])
    
        #選ばない時
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

#print(dp)
print(int(dp[n][w]))

### FIXED CODE ###

#import numpy as np
n,w=map(int,input().split())
#重さをdpにする
#dp=[[0]*n,[0]*w] #n番目の品,重さ。価値が値として入る
#dp=np.zeros((n+1,w+1))
dp=[[0] * (w+1) for i in range(n+1)]
#print(dp)
#print(len(dp[0]))
#print(len(dp[n][w]))
W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W+=[a]
    V+=[b]

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_w in range(w+1):
        #print(sum_w)
        #足した時に価値が上がるケース
        if sum_w>=W[i]:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - W[i]] + V[i])
    
        #選ばない時
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

#print(dp)
print(int(dp[n][w]))
### BUGGY CODE ###

import copy
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)
for i in range(n):
  x.pop(i)
  x.sort()
  print(x[int((n - 1) / 2)])
  del x[:] 
  for j in z:
    x.append(j)

### FIXED CODE ###

import copy
import statistics
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)
z.sort()
t = (z[int(n / 2) - 1] + z[int(n / 2)]) / 2

for i in range(n):
  if x[i] < t:
    print(z[int(n / 2)])
  else:
    print(z[int(n / 2) - 1])
### BUGGY CODE ###

INF = float("Inf")
n,m,l = map(int, input().split())
G = [[INF]*n for i in range(n)]
for i in range(n):
    G[i][i] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    a,b = a-1,b-1
    if c <= l:
        G[a][b] = G[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if G[i][k]!=INF and G[k][j]!=INF:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

#最短経路がL以下の部分について、edgeをつなぐ
GG = [[INF]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            GG[i][j] = 0
        else:
            if G[i][j] <= l:
                GG[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if GG[i][k]!=INF and GG[k][j]!=INF:
                GG[i][j] = min(GG[i][j], GG[i][k] + GG[k][j])

q = int(input())
ans = []
for i in range(q):
    s,t = map(int, input().split())
    a = GG[s-1][t-1]
    if a == INF:
        a = 0
    ans.append(a-1)
print(*ans, sep="\n")

### FIXED CODE ###

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

def main():
    INF = float("Inf")
    n,m,l = map(int, input().split())
    G = [[INF]*n for i in range(n)]
    for i in range(n):
        G[i][i] = 0
    for i in range(m):
        a,b,c = map(int, input().split())
        a,b = a-1,b-1
        if c <= l:
            G[a][b] = G[b][a] = c
    G = floyd_warshall(G, directed=False)
    G = np.where(G <=l, 1, INF)
    for i in range(n):
        G[i][i] = 0
    GG = floyd_warshall(G, directed=False)

    q = int(input())
    ans = []
    for i in range(q):
        s,t = map(int, input().split())
        a = GG[s-1][t-1]
        if a == INF:
            a = 0
        else:
            a = int(a)
        ans.append(a-1)
    print(*ans, sep="\n")

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

n=int(input())
a=list(map(int,input().split()))
dig=1
ans=0
m=max(a)
k=0
mod=10**9+7
while m>>k >0:
    k+=1
k=max(0,k)
for j in range(k):
    cnt=0
    for i in range(n):
        if a[i]>>j & 1:
            cnt+=1
    cnt=cnt*(n-cnt)%mod
    ans=(ans+dig*cnt%mod)%mod
    dig=dig*2%mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dig=1
ans=0
m=max(a)
k=0
mod=10**9+7
while m>>k >0:
    k+=1
k=max(0,k)
for j in range(k):
    cnt=0
    for i in range(n):
        if a[i]>>j & 1:
            cnt+=1
    cnt=cnt*(n-cnt)%mod
    ans=(ans+dig*cnt%mod)%mod
    dig=dig*2%mod
print(ans)
### BUGGY CODE ###

n = int(input())
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx+1, len(An)):
            if An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                   flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

### FIXED CODE ###

n = int(input())
An = list(map(int, input().split()))

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))
### BUGGY CODE ###

import math

#Input
H, N = map(int, input().split())
lstV = list()
lstC = list()
for i in range(N):
    value, cost = map(int, input().split())
    lstV.append(value)
    lstC.append(cost)

#DPMap
inf = 2**31 - 1
dp = list([inf]*(H + max(lstV)))
dp[0] = 0
for i in range(0,len(dp)):
    if dp[i] != inf:
        for j in range(0,len(lstV)):
            value = lstV[j]
            cost = lstC[j]
            if i + value <= len(dp) - 1:
                dp[i + value] = min(dp[i + value], dp[i] + cost)
print(min(dp[H:]))

### FIXED CODE ###

H, N = map(int, input().split())
AB = list(list(map(int, input().split())) for _ in range(N))

def main2(H, N, AB):
    inf = 2**31 -1
    dp = [inf] * (H + max(a for a, _ in AB))
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = min(dp[i-a]+b for a,b in AB)
    print(min(dp[H:]))

main2(H,N,AB)
### BUGGY CODE ###

# coding:utf-8                                                                  

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = []
posy = [0]
for i, s in enumerate(ss):
    if i == 0:
        posx.append(len(s))
    elif i % 2 == 0:
        xs.append(len(s))
    else:
        ys.append(len(s))

for x in xs:
    tmpx = []
    for px in posx:
        tmpx.append(px+x)
        tmpx.append(px-x)
    set(tmpx)
    posx = tmpx

for y in ys:
    tmpy = []
    for py in posy:
        tmpy.append(py+y)
        tmpy.append(py-y)
    set(tmpy)
    posy = tmpy

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"



### FIXED CODE ###

# coding:utf-8                                                                  

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = set()
posy = set()
posy.add(0)
for i, s in enumerate(ss):
    if i == 0:
        posx.add(len(s))
    elif i % 2 == 0:
        xs.append(len(s))
    else:
        ys.append(len(s))

for x in xs:
    tmpx = set()
    for px in posx:
        tmpx.add(px+x)
        tmpx.add(px-x)
    posx = tmpx

for y in ys:
    tmpy = set()
    for py in posy:
        tmpy.add(py+y)
        tmpy.add(py-y)
    posy = tmpy

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"
### BUGGY CODE ###

n = int(input())
dp = [0]*(n+1)
for i in range(2,n+1):
    j = 2
    while 1:
        if i*j <= n:
            dp[i*j] += 1
        else:
            break
        j += 1
ans = 0
for i in range(2,n+1):
    ans += i*dp[i]
print(ans+n*(n+1)-1)

### FIXED CODE ###

n = int(input())
dp = [0]*(n+1)
for i in range(2,n+1):
    j = 2
    while 1:
        if i*j <= n:
            dp[i*j] += 1
        else:
            break
        j += 1
ans = 0
for i in range(2,n+1):
    ans += i*dp[i]
print(ans+n*(n+1)-1)
### BUGGY CODE ###

A, B, K = [int(i) for i in input().split()]
for i in range(A, B+1):
    if i < A + K or B - K < i:
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
if B - A < 2 * K:
    print(*range(A, B + 1), sep="\n")
else:
    print(*range(A, A + K), sep="\n")
    print(*range(B - K + 1,  B + 1), sep="\n")
### BUGGY CODE ###

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

for i in range(M):
    A.sort()
    for j in range(q[i][0]):
        if A[j]<q[i][1]:
            A[j]=q[i][1]
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for _ in range(m)]

A.sort()
BC.sort(key=lambda x: x[1], reverse=True)

cnt = 0
for b, c in BC:
    for i in range(b):
        if c < A[cnt]:
            break
        A[cnt] = c
        cnt += 1
        if cnt >= n:
            break
    else:
        continue
    break

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

import collections
N = int(input())
A = [0]
A += list(map(int, input().split()))
cnt = 0
L = [- 10 ** 6]
R = [- 10 ** 6]

for i in range(1, N + 1):
    L.append(i + A[i])
    R.append(i - A[i])
for j in range(1, N + 1):
    cnt += L.count(R[j])

print(cnt)

### FIXED CODE ###

import collections
N = int(input())
A = [0]
A += list(map(int, input().split()))
cnt = 0
L = [- 10 ** 6]
R = [- 10 ** 6]

for i in range(1, N + 1):
    L.append(i + A[i])
    R.append(i - A[i])
c = collections.Counter(L)

for j in range(1, N + 1):
    cnt += c.get(R[j], 0)
print(cnt)
### BUGGY CODE ###

def f(n):
    mx = 0
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i, dpv in enumerate(dp[s::-1]):
            nv = dpv + v
            ni = s + w - i
            if nv > dp[ni]:
                dp[ni] = nv
                if nv > mx:
                    mx = nv
    print(mx)


n = int(input())
f(n)


### FIXED CODE ###

def f(n):
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
    print(max(dp))


n = int(input())
f(n)
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    n, q = map(int, input().split())
    s = input()
    l = []
    r = []
    for _ in range(q):
        li, ri = map(int, input().split())
        l.append(li-1)
        r.append(ri-1)

    # x[i] = 0文字目からi文字目までのACの出現回数の総和
    y = [i for i, v in enumerate(s) if i < n - 1 and s[i] + s[i+1] == 'AC']
    x = []
    for i in range(n):
        before = 0 if len(x) == 0 else x[-1]
        if i in y:
            x.append(before + 1)
        else:
            x.append(before)
    for i in range(q):
        li = l[i]
        ri = r[i]
        lsum = 0 if li == 0 else x[li-1]
        rsum = x[ri-1]
        print(rsum - lsum)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def main():
    n, q = map(int, input().split())
    s = input()
    x = [0] * n
    if s[0:2] == 'AC':
        x[0] = 1
    for i in range(n - 1):
        if s[i+1:i+3] == 'AC':
            x[i+1] = x[i] + 1
        else:
            x[i+1] = x[i]

    for _ in range(q):
        li, ri = map(int, input().split())
        li -= 1
        ri -= 1
        lsum = 0 if li == 0 else x[li-1]
        rsum = x[ri-1]
        print(rsum - lsum)

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

from collections import deque

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True
        for edge in graph[v]:
            u = edge[0]
            d = edge[1]
            if(dist[u] == int(1e10)):
                dist[u] = dist[v] + d
                Q.append(u)
            else:
                if(dist[u] != dist[v] + d):
                    print("No")
                    exit()

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

graph = [[] for i in range(N)] 

for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])

visited = [False] * N

for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")




### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")
### BUGGY CODE ###

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

L.sort()

class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return True
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return False

class Data():
  class Node():
    def __init__(s):
      s.R = {}
      s.reset()
    def reset(s):
      s.done = False
      s.cos = -1
    def set(s, a, x):
      s.R[a] = x

  def __init__(s, N):
    s.nodes = [s.Node() for _ in range(N)]
  def set(s, a, b, x):
    s.nodes[a].set(b, x)
    s.nodes[b].set(a, x)
  def dist(s, a, b, f):
    if f:
      s.dijk(a)
    return s.nodes[b].cos
  def dijk(s, a):
    for n in s.nodes:
      n.reset()
    s.nodes[a].cos = 0
    while True:
      dn = None
      for n in s.nodes:
        if n.done or n.cos < 0: continue
        if dn == None or n.cos < dn.cos:
          dn = n
      if dn == None:
        break
      dn.done = True
      for k, v in dn.R.items():
        n = s.nodes[k]
        if n.done: continue
        if n.cos == -1 or n.cos > dn.cos + v:
          n.cos = dn.cos + v
t = Tree(N)
d = Data(N)
ans = 0
for i in range(len(L)):
  x, a, b = L[i]
  if t.merge(a, b):
    if d.dist(a, b, True) != x:
      d.set(a, b, x)
      ans += x
  else:
    d.set(a, b, x)
    ans += x

for i in range(N - 1):
  if d.dist(i, i + 1, True) != A[i][i + 1]:
    break
  for j in range(i + 2, N):
    if d.dist(i, j, False) != A[i][j]:
      break
  else:
    continue
  break
else:
  print(ans)
  exit()

print(-1)



### FIXED CODE ###

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if A[i][j] > A[i][k] + A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k] + A[k][j]:
        break
    else:
      ans += A[i][j]

print(ans)