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

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
# スペース区切りの整数の入力
ar = []
for i in range(n):
  ar.append("".join(sorted(input())))

#for t in ar:
#  print(t)
for i in range(n):
  for j in range(i+1, n):
    if ar[i] == ar[j]:
      ar[j] = ar[i]

count = 0
#for i in range(n):
#  for j in range(i+1, n):
#    if ar[i] is ar[j]:
#      count = count + 1

for i in range(n):
  count = count + ar[i+1:].count(ar[i])

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())

# スペース区切りの整数の入力
ar = []
for i in range(N):
  l = list(input())
  l.sort()
  ar.append("".join(l).__hash__())

# 数を数える
list = {}
for i in ar:
  if i in list:
    list[i] = list[i] + 1
  else:
    list[i] = 1
  
count = 0
for i in list.values():
  n = i - 1
  count = count + int(((n * (n + 1)) / 2))

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

from operator import mul
from functools import reduce

def ncr(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

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
if K == 1:
    print(0)
    exit()

A = sorted(list(map(int, input().split())))
acmA = []
for i in range(N):
    if i == 0:
        acmA.append(A[i])
    else:
        acmA.append((A[i]+acmA[i-1]))
ans = 0
sum_num = 0
for i in range(N - (K - 1)):
    for j in range(i+K-1, N):
        ans += (A[j] - A[i]) * ncr(j-i-1, K-2) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
for i in range(N - K + 1):
    ans += ((A[-1-i] - A[i]) % MOD * ncr(N - i - 1, K - 1)) % MOD
print(ans % MOD)
### BUGGY CODE ###

from numba import jit

@jit
def solve():
    
    s = list(input())[::-1]
    num = len(s)
    #print(s, num)
    
    l = []
    for i in range(1,num+1):
        l.append(int(''.join(s[:i][::-1])))
    #print(l)
    
    mod = []
    for j in range(num):
        mod.append(l[j] % 2019)
    #print(mod)
    
    ans = 0
    for p in range(num):
        if mod[p] == 0:
            ans += 1
        tmp = 1
        for q in range(p+1,num):
            if mod[p] == mod[q]:
                tmp += 1
        ans += (tmp-1)*tmp//2
    
    print(ans)

solve()

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

N, M= [int(i) for i in input().split(' ')]
graph = {}
 
for i in range(1,N+1):
  graph[i] = []
 
for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    
 
def bfs(graph, start):
  queue = [start]
  miti = [-1 for _ in range(N)]

  while queue:
    label = queue.pop(0)
    for i in graph[label]:
      if miti[i-1] < 0:
        queue.append(i)
        miti[i-1] = label
  return miti
 
miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i-1])
else:
  print('No')

### FIXED CODE ###

N, M= [int(i) for i in input().split(' ')]
graph = {}
 
for i in range(1,N+1):
  graph[i] = []
 
for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    
 
def bfs(graph, start):
  queue = [start]
  miti = [-1 for _ in range(N)]

  while queue:
    label = queue.pop(0)
    for i in graph[label]:
      if miti[i-1] < 0:
        queue.append(i)
        miti[i-1] = label
  return miti
 
miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i-1])
else:
  print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for sideL in range(N):
    for sideR in range(sideL + 1, N)[::-1]:

        setX = set(ptsX[sideL:sideR + 1])
        if len(setX) < K: break

        lenX = ptsX[sideR][0] - ptsX[sideL][0]

        for sideB in range(N):
            for sideT in range(sideB + 1, N)[::-1]:
                
                setY = set(ptsY[sideB:sideT + 1])
                if len(setY) < K: break

                num = len(setX & setY)
                if num < K: break

                lenY = ptsY[sideT][1] - ptsY[sideB][1]
                area = lenX * lenY

                if num == K:
                    ans = min(ans, area)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for iLeft, ptLeft in enumerate(ptsX):
    setX = set(ptsX[iLeft:])

    for ptRight in ptsX[iLeft + 1:][::-1]:
        if len(setX) < K: break
        lenX = ptRight[0] - ptLeft[0]

        for iBottom, ptBottom in enumerate(ptsY):
            setY = set(ptsY[iBottom:])

            for ptTop in ptsY[iBottom + 1:][::-1]:
                if len(setY) < K: break

                num = len(setX & setY)
                if num < K: break

                if num == K:
                    lenY = ptTop[1] - ptBottom[1]
                    area = lenX * lenY
                    ans = min(ans, area)

                setY.remove(ptTop)

        setX.remove(ptRight)

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

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

c=0
d=a

for i in range(a,b+1):
    if d%x==0:
        c=c+1
    d=d+1
    
print(c)

### FIXED CODE ###

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

c=b//x-(a-1)//x
    
print(c)
### BUGGY CODE ###

from collections import deque

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

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


ans = 0

que = deque()

for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            que.append((i, j))

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "#"
                que.append((nny, nnx))

    ans += 1

while check(field):
    one_bsf()
    
print(ans)

### FIXED CODE ###

from collections import deque

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

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


ans = 0

que = deque()

num_white = H * W

paint = 0

for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            que.append((i, j))
            num_white -= 1

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global paint
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "#"
                paint += 1
                que.append((nny, nnx))

    ans += 1

while num_white != paint:
    one_bsf()
    
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
ans = 1
for i in range(1,n):
    if x[i] == min(x[:i+1]):
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
ans = 1
b = x[0]
for i in range(1,n):
    if x[i] < b:
        ans += 1
        b = x[i]
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
B =[]
C =[]

l = [list(map(int,input().split())) for i in range(M)]

A.sort()
l = sorted(l,key = lambda x:x[1])

flag =False
for i in l[::-1]:
    for j in A[:i[0]]:
        k = i[1]
        if j<k:
            if len(A)>1:
                A = A[1:]
                A.append(k)
            else:
                A[0] = k
        else:
            flag = True
            break
    if flag:
        break
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
l = [list(map(int,input().split())) for i in range(M)]

A.sort()
l = sorted(l,key = lambda x:x[1])

ind =0
for b,c in l[::-1]:
    mx = min(N,ind+b)
    for i in range(ind,mx):
        if c>A[i]:
            A[i] = c
    if mx==N:
        break
    ind += b
print(sum(A))
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

# dp = [[[False]*1009 for _ in range(4)] for _ in range(30009)]
dp = np.zeros((N+9, 4, 1009))
# dp[0][0][0] = True
dp[0, 0, 0] = 1

for i in range(N):
    for j in range(4):
        for k in range(1000):
            # jif not dp[i][j][k]:
            if not dp[i, j, k]:
                continue

            dp[i + 1, j, k] = 1
            if j <= 2:
                dp[i+1, j+1, k*10 + int(S[i])] = 1

print(int(np.sum(dp[N, 3, :])))


### FIXED CODE ###

def ok(target, S):
    for t in target:
        if t in S:
            S = S[S.index(t)+1:]
        else:
            return False
    return True


N = int(input())
S = input()
ans = 0

for i in range(0, 999+1):
    target = str(i).zfill(3)
    ans += ok(target, S)

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

import re
if __name__ == '__main__':
    s = input()
    t = input()

    str_mat = [list('.'*len(t)), list(t)]

    bin_str_dict = {}
    for i in range(0, 2 ** len(t)):
        bin_str = format(i, 'b').zfill(len(t))
        if not bin_str.count('0') in bin_str_dict:
            bin_str_dict[bin_str.count('0')] = [bin_str]
        else:
            bin_str_dict[bin_str.count('0')].append(bin_str)

    def judge(i):
        for pattern in bin_str_dict[i]:
            pattern = ''.join([str_mat[int(bin_num)][index] for index, bin_num in enumerate(pattern)])
            if re.search(pattern, s):
                return True
        return False

    for i in range(0, len(t)):
        flag = judge(i)
        if flag:
            print(i)
            break
    if not flag:
        print(len(t))

### FIXED CODE ###

if __name__ == '__main__':
    s = list(input())
    t = list(input())

    max_score = 0
    if len(s) == len(t):
        max_score = sum([s[j] == t[j] for j in range(len(t))])
    else:
        for i in range(0, len(s) - len(t)):
            score = sum([s[i + j] == t[j] for j in range(len(t))])
            if max_score < score:
                max_score = score
    print(len(t) - max_score)
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            p = math.gcd(i,j)
            ans += math.gcd(p,k)

print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            p = math.gcd(i,j)
            ans += math.gcd(p,k)
 
print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())

ans=1
for i in range(1,100000000):
  tmp=i**n
  if (p>=tmp) and (p%tmp == 0):
   ans=i
  if(p<tmp):
    break
print(ans)

### FIXED CODE ###

n,p=map(int,input().split())

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)
### BUGGY CODE ###

from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

C=[0]*(N-1)
G=[set() for _ in range(N+1)]

T={i:False for i in range(1,N+1)}
T[1]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)

            p,q=min(v,w),max(v,w)
            c=1
            while c in G[p]|G[q]:
                c+=1
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)

print(max(C))
print("\n".join(map(str,C)))

### FIXED CODE ###

from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

M=max(F)

C=[0]*(N-1)
G=[set() for _ in range(N+1)]
A=[-1]*(N+1)

T={i:False for i in range(1,N+1)}
T[1]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    y=1
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)
            
            p,q=min(v,w),max(v,w)

            c=(A[v]+y)%M
            
            A[w]=c
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)
            y+=1

print(max(C)+1)
print("\n".join(map(lambda x:str(x+1),C)))
### BUGGY CODE ###

import fractions as math
def main():
    A,B=map(int, input().split())
    gcd_ab = math.gcd(A,B)
    ans={1}
    i = 2
    while (A>=i and B>=i) and (i <= gcd_ab):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
            gcd_ab = math.gcd(A,B)
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    ans = factorization(gcd(A,B))
    if ans[0][0] == 1:
        print(1)
    else:
        print(len(ans)+1)

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

# 最も単純にやると
# 盤面の移動のしかたはN^2通り
# それぞれに対して、対称行列かの判定はO(N^2)個の条件を確認する必要がある
# したがってO(N^4)である。間に合わない。
# しかし、対称行列であれば、1行1列を右下に移動しても対称行列である。
# これより、行またはだけを移動した場合について確認すれば良い。O(N^3)。

n = int(input())
masume = [input() for i in range(n)]

count = 0
for diff in range(n):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            if masume[(i+diff)%n][j] != masume[(j+diff)%n][i]:
                flag = False
                break
        if not flag:
            break
    count += flag

print(count * n)


### FIXED CODE ###

# 最も単純にやると
# 盤面の移動のしかたはN^2通り
# それぞれに対して、対称行列かの判定はO(N^2)個の条件を確認する必要がある
# したがってO(N^4)である。間に合わない。
# しかし、対称行列であれば、1行1列を右下に移動しても対称行列である。
# これより、行またはだけを移動した場合について確認すれば良い。O(N^3)。

n = int(input())
masume = [input() for i in range(n)]

count = 0
for diff in range(n):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            if masume[(i+diff)%n][j] != masume[(j+diff)%n][i]:
                flag = False
                break
        if not flag:
            break
    count += flag

print(count * n)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
sum_ = 0
while K > 0:
    if A > 0:
        sum_ += 1
        A -= 1
    elif B > 0:
        B -= 1
    elif C > 0:
        sum_ -= 1
        C -= 1
    K -= 1
print(sum_)

### FIXED CODE ###

A,B,C,K = map(int,input().split())
sum_ = 0
if K < A:
    sum_ = K
elif K <= B:
    sum_ = A
else:
    sum_ = A - (K-A-B)
print(sum_)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = list(set(d))

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      if dist[child] > dist[node] + 1:
        dist[child] = dist[node] + 1
        d.append([child, node])
      if child == T:
        print(dist[child])
        quit()

print(-1)

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u, v = 3*(u - 1), 3*(v - 1)
  graph[u].append(v+1)
  graph[u+1].append(v+2)
  graph[u+2].append(v)

s, t = map(int, input().split())
s, t = 3*(s - 1), 3*(t - 1)


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(m):
    a.sort()
    b, c = map(int, input().split())
    idx = bisect.bisect_right(a, c)
    if idx > b:
        end = b
    else:
        end = idx
    for i in range(end):
        a[i] = c

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []

for _ in range(m):
    l.append(list(map(int, input().split())))

a.sort()
l.sort(key=lambda x: x[1], reverse=True)

focus = 0
for b, c in l:
    for j in range(focus, min(focus+b, n)):
        a[j] = max(c, a[j])
    focus += b

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

class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()
### BUGGY CODE ###

# -*- coding utf-8 -*-

a,b,x=map(int,input().split())
ans=0

for i in range(a,b+1):
    if i%x==0:
        ans+=1
    else:
        ans+=0
print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

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

print(b//x - (a-1)//x  )
### BUGGY CODE ###

n,q = map(int,input().split())
s=list(input())	
	
flag = False
ans = 0
for i in range(q):
    ans = 0
    l,r = map(int,input().split())
    s2 = s[l-1:r]
    for word in s2:
        if word == "A":
            flag = True
        elif word == "C":
            if flag:
                ans += 1
                flag = False
        else:
            flag = False

    print(ans)


### FIXED CODE ###

n,q = map(int,input().split())
#s=list(input())	
s = input()
index = -1
indexes = []
while True:
    index = s.find("AC", index + 1)
    if index == -1:
        break
    indexes.append(index)
dp = []

for i in range (n):
    dp.append(len(indexes))
    if len(indexes)> 0 and indexes[0] == i:
        indexes.pop(0)
for i in range(q):
    l,r = map(int,input().split())
    print(dp[l-1] - dp[r-1])
### BUGGY CODE ###

A,B,C,K=map(int,input().split())
for i in range(C+1):
    for j in range(B+1):
        for k in range(A+1):
            if i+j+k==K:
                print(-1*i+k)
                exit()

### FIXED CODE ###

A,B,C,K=map(int,input().split())
if A>=K:
    print(K)
elif A+B>=K:
    print(A)
else:
    print(A-(K-A-B))
### BUGGY CODE ###

s = list(map(str, input()))
bool = True
while bool == True:
    for i in range(len(s)):
        if i%2 == 0 and s[i] == 'R' or s[i] == 'U' or s[i] == 'D':
            bool = True
        elif i%2 == 1 and s[i] == 'L' or s[i] == 'U' or s[i] == 'D':
            bool = True
        else:
            bool = False
        
if bool == True:
    print('Yes')
elif bool == False:
    print('No')

### FIXED CODE ###

S = list(map(str, input()))

bool = True
i = 0
while i != len(S):
    if i%2 == 0 and S[i] == 'R' or S[i] == 'U' or S[i] == 'D':
        bool = True
        i += 1
    elif i%2 == 1 and S[i] == 'L' or S[i] == 'U' or S[i] == 'D':
        bool = True
        i += 1
    else:
        bool = False
        i = len(S)
        
if bool:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [True] *(N*N)
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i*N+j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i*N+j]:
                ans += A[i][j]
print(ans)

### 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()