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

def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        m = j
        for k in list13:
          dpi1[lut[m]] += dpi[k]
          m += 10
    else:
      m = int(s[i])
      for k in list13:
        dpi1[lut[m]] += dpi[k]
        m += 10
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

A,B,C=map(int,input().split())
cnt=0
for i in range(A,B+1):
  if i%C==0:
    cnt+=1
print(cnt)

### FIXED CODE ###

A,B,C=map(int,input().split())
A=(A-1)//C
B=B//C
print(B-A)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

#初期 
SUM = sum(P[0:K])
M=0

for i in range(N - K + 1):
    _SUM=sum(P[i:i + K])
    if SUM < _SUM:
        SUM = _SUM
        M = i

EXP_V = (K + SUM)/2
print(EXP_V)

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

#初期
SUM = [0]*N
SUM[0] = sum(P[0:K])

for i in range(N - K):
    SUM[i+1] = SUM[i]-P[i] + P[i+K]

EXP_V = (K + max(SUM))/2
print(EXP_V)
### BUGGY CODE ###

n = int(input())
s = list(input())
r = [i for i, x in enumerate(s) if x == "R"]
b = [i for i, x in enumerate(s) if x == "B"]
g = [i for i, x in enumerate(s) if x == "G"]
ans = len(r) * len(b) * len(g)
for i in r:
    for j in g:
        i_ = min(i, j)
        j_ = max(i, j)
        div = (j_ - i_)
        if i_ - div in b:
            ans -= 1
        if div % 2 == 0:
            k_2 = div // 2 + i_
            if div // 2 + i_ in b:
                ans -= 1
        if div + j_ in b:
            ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
r = [i for i, x in enumerate(s) if x == "R"]
g = [i for i, x in enumerate(s) if x == "G"]
b = [i for i, x in enumerate(s) if x == "B"]
ans = len(r) * len(g) * len(b)

for i in r:
    for j in g:
        i_ = min(i, j)
        j_ = max(i, j)
        div = (j_ - i_)
        k_1 = i_ - div
        k_2 = div // 2 + i_
        k_3 = div + j_
        if k_1 >= 0 and s[k_1] == "B":
            ans -= 1
        if div % 2 == 0 and s[k_2] == "B":
            ans -= 1
        if k_3 < n and s[k_3] == "B":
            ans -= 1
print(ans)
### BUGGY CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range(n//c+1):
        if (n - b*y - c*z) % a == 0 and (n - b*y - c*z) >= 0:
            count += 1
print(count)

### FIXED CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range((n-y*b)//c+1):
        if (n - b*y - c*z) % a == 0:
            count += 1
print(count)
### BUGGY CODE ###

N,K=map(int,input().split())
h=[]
for i in range(0,N):
    h.append(int(input()))
h_New=[]
for i in range(0,N):
    a=min(h)
    h_New.append(a)
    h.remove(a)
h_k=[]
for i in range(0,N-K+1):
    h_k.append(h_New[i+K-1]-h_New[i])
print(min(h_k))

### FIXED CODE ###

def merge(a,b): #整列済みの配列aとbを併合
    r =[]
    #結果の格納先を用意
    ai = 0 #aは何番目まで処理したか?
    bi = 0 #bは何番目まで処理したか?
    for i in range(0, len(a)+len(b)):
        if (bi >= len(b) or (ai < len(a) and a[ai] < b[bi])):
         #aとbの先頭を比較(長さを超えないよう注意)
            r.append(a[ai])
            ai = ai + 1
        else:
            r.append(b[bi])
            bi = bi + 1 #aとbの先頭の小さい方をrへ
    return r
def mergesort(a): #配列aを整列
    n = len(a)
    if n <= 1: #短いときはそれでよし
        return a
    else:
        l = mergesort(a[0 : n//2])
        r = mergesort(a[n//2 : n])
        #前半と後半をそれぞれ整列
        return merge(l,r)
        #整列した結果を併合
N,K=map(int,input().split())
h=[]
for i in range(0,N):
    h.append(int(input()))
h_New=mergesort(h)
h_k=[]
for i in range(0,N-K+1):
    h_k.append(h_New[i+K-1]-h_New[i])
print(min(h_k))
### BUGGY CODE ###

N = int(input())
count = 1+N
for i in range(1,N):
  if N % i == 0 and i + N/i < count:
    count = i+ N/i
count = int(count)
print(count-2)


### FIXED CODE ###

N = int(input())
count = 1+N
for i in range(1,int(N**0.5)+1):
  if N % i == 0 and i + N/i < count:
    count = i+ N/i
count = int(count)
print(count-2)
### BUGGY CODE ###

from fractions import gcd

k = int(input())
ans = 0
g = []

for a in range(1,k+1):
  g.append(a)

o = []
for b in range(1,k+1):
    for i in g:
      o.append(gcd(b,i))


for c in range(1, k+1):
  for i in o:
    ans += gcd(c,i)

print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for g in range(1,k+1):
      ans += gcd(gcd(i,j), g)

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

S=list(map(int,list(input())))
N=len(S)

remainder=[0]*2019
val=0
ans=0
for i in range(1,N+1):
  val+=S[-i]*(10**(i-1))
  n=val%2019
  remainder[n]+=1
  if remainder[n]!=1:
    ans+=remainder[n]-1

ans+=remainder[0]
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

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

def yoi(s, a, b):
  for i in range(n):
    for j in range(n):
      if s[(i + a) % n][(j + b) % n] != s[(j + a) % n][(i + b) % n]:
        return 0
  return 1

sol = sum(yoi(s, a, b) for a in range(n) for b in range(n))
print(sol)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
st = [str().join(s_) for s_ in zip(*s)]

sol = 0

for i in range(n):
    for k in range(n):
        if s[k] != st[k]:
            break
    else:
        sol += 1
    
    s = [s_l[1:]+s_l[0] for s_l in s]
    st = st[1:] + [st[0]]
    
print(sol * n)
### BUGGY CODE ###

N = int(input())
S = ""
List = []
for i in range(N):
    S = input()
    List.append(S)
New_List = []
for j in List:
    if j not in New_List:
        New_List.append(j)
print(len(New_List))

### FIXED CODE ###

N = int(input())
List = []
for i in range(N):
    S = input()
    List.append(S)
print(len(set(List)))
### BUGGY CODE ###

import sys
import bisect
import heapq
sys.setrecursionlimit(10 ** 7)

# TLE

N, Q = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 0, x))
    EVENT.append((t-x, 1, x))

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        ans[x] = STOP[0]
    elif op == 0:
        heapq.heappush(STOP, x)
    elif op == 1:
        STOP.remove(x)
        heapq.heapify(STOP)


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

N, M, R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
from itertools import permutations
perm = permutations(r, R)
INF = float("inf")
dp = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
ans = INF
for p in perm:
    tmp = 0
    p = list(p)
    for i in range(R-1):
        tmp += dp[p[i]][p[i+1]]
    ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
edges = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b,c))
    edges[b].append((a,c))
V = N
INF = float("inf")
dp = [[INF]*V for _ in range(V)]
for i in range(V):
    for j, w in edges[i]:
        dp[i][j] = w
for k in range(V):
    for i in range(V):
        for j in range(V):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = INF
for p in permutations(r):
    t = 0
    for i in range(1, R):
        t += dp[p[i]][p[i-1]]
    ans = min(ans, t)
print(ans)
### BUGGY CODE ###

import numpy as np
#import numba
#@numba.jit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=np.int16)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=np.array([ord(i) for i in input()])
solve(n,s)

### FIXED CODE ###

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

# D - Lamp

#import numpy as np

H, W = map(int, input().split())
#S = np.array([list(input()) for _ in range(H)])
S = [list(input()) for _ in range(H)]

def trans(M):
    output_list = []
    for col in range(len(M[0])):
        tmp = []
        for row in range(len(M)):
            tmp.append(M[row][col])
        output_list.append(tmp)
    return output_list
            
def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

#n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
ans = 0
tmp1 = n_matrix_lighten(S)
tmp2 = trans(n_matrix_lighten(trans(S)))

for row in range(H):
    for col in range(W):
        ans = max(ans, tmp1[row][col] + tmp2[row][col] - 1)

print(ans)

### FIXED CODE ###

# D - Lamp

#import numpy as np

H, W = map(int, input().split())
#S = np.array([list(input()) for _ in range(H)])
S = [list(input()) for _ in range(H)]

def trans(M):
    output_list = []
    for col in range(len(M[0])):
        tmp = []
        for row in range(len(M)):
            tmp.append(M[row][col])
        output_list.append(tmp)
    return output_list
            
def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

#n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
ans = 0
tmp1 = n_matrix_lighten(S)
tmp2 = trans(n_matrix_lighten(trans(S)))

for row in range(H):
    for col in range(W):
        ans = max(ans, tmp1[row][col] + tmp2[row][col] - 1)

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

import bisect
n = int(input())
As = list(map(int, input().split()))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = [0]*n
for idx, b in enumerate(Bs):
    cnt[idx] = len(Cs) - bisect.bisect_right(Cs, b)

print(sum([sum(cnt[bisect.bisect_right(Bs, a):]) for a in As]))


### FIXED CODE ###

import bisect
n = int(input())
As = list(map(int, input().split()))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = [0]*(n+1)
v = 0
for idx, b in enumerate(Bs[::-1]):
    v += len(Cs) - bisect.bisect_right(Cs, b)
    cnt[n-1-idx] = v

print(sum([cnt[bisect.bisect_right(Bs, a)] for a in As]))
### BUGGY CODE ###

import copy
n=int(input())
A=[]
B=[]
for i in range(0,n):
    A.extend([int(input())])
for j in range(0,n):
    B=copy.copy(A)
    s=A[j]
    A.pop(j)
    print(max(A))
    A = copy.copy(B)

### FIXED CODE ###

import copy
from sys import stdin
n=int(input())
A=[int(stdin.readline().rstrip()) for _ in range(n)]
z=max(A)
B=sorted(A)
o=B[n-2]
for j in range(0,n):
    if A[j]<z:
       print(z)
    else:
        if B[n-2]==B[n-1]:
           print(z)
        else:
           print(o)
### BUGGY CODE ###

import copy
import itertools
    
h,w = (int(x) for x in input().split())
ab = []
step = []
count = 0
for i in range(h):
    a = list(input())
    ab.append(a+['#'])
    for j in range(w):
        if a[j] == '#':
            step.append([i,j])

ab.append(list('#'*w))           
memo_step = copy.deepcopy(step)

dp = [[0 for a in range(w)] for b in range(h)]
 
while len(step) > 0:
    y, x = step.pop(0)
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 and -1 < x < w and -1 < y < h :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 and -1 < x < w and -1 < y < h :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 and -1 < x < w and -1 < y < h :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 and -1 < x < w and -1 < y < h :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1

for i,j in memo_step:
    dp[i][j] = 0

mx = max(list(itertools.chain.from_iterable(dp)))
 
print(mx)


### FIXED CODE ###

from collections import deque
 
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]
 
painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])
 
ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d
 
print(ans)
### BUGGY CODE ###

N=int(input())
A=[[tuple(map(int,input().split(' ')))for j in range(int(input()))] for i in range(N)]
say_map=[[-1 for i in range(N)] for j in range(N)]
ans = 0
for n,i in enumerate(A):
    for j,k in i:
        say_map[n][j-1]=k
for i in range(2**N):
    i_bin=format(i,'0{}b'.format(N))
    flg = True
    tmp = 0
    for n,j in enumerate(i_bin):
        j = int(j)
        if j == 1:
            tmp += 1
            for k,l in zip(i_bin,say_map[n]):
                if (int(k)==0 and l==1) or (int(k)==1 and l ==0):
                    flg=False
                    break
            if not flg:
                tmp = 0
                break
    ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

N=int(input())
A=[[tuple(map(int,input().split(' ')))for j in range(int(input()))] for i in range(N)]
say_map=[[-1 for i in range(N)] for j in range(N)]
ans = 0
for n,i in enumerate(A):
    for j,k in i:
        say_map[n][j-1]=k
for i in range(2**N):
    i_bin=format(i,'0{}b'.format(N))
    flg = True
    tmp = 0
    for n,j in enumerate(i_bin):
        j = int(j)
        if j == 1:
            tmp += 1
            for k,l in zip(i_bin,say_map[n]):
                if (int(k)==0 and l==1) or (int(k)==1 and l ==0):
                    flg=False
                    break
            if not flg:
                tmp = 0
                break
    ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

candidate = [-float('inf')]
for i in range(1, len(stack)):
    for r1, r2 in zip(stack[::1], stack[i::1]):
        candidate.append(r2 - r1)
    candidate = [max(candidate)]

print(candidate[0])

### FIXED CODE ###

n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

maxv = -10**9
minv = stack[0]
for i in range(1, len(stack)):
    maxv = max(maxv, stack[i] - minv)
    minv = min(minv, stack[i])

print(maxv)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and rr-ll >= 2:
        # print("rr",rr,"ll",ll)
        t = s - A[rr]
        if t>s:
            break
        # print("s",s,"t",t)
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            # print("r",r,"l",l,"m",m)
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            # print(ans)
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        # print(A)
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and s <= A[rr]:
        rr -= 1
    while rr >= 1 and rr-ll >= 2:
        # print("rr",rr,"ll",ll)
        t = s - A[rr]

        # print("s",s,"t",t)
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            # print("r",r,"l",l,"m",m)
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            # print(ans)
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        # print(A)
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)
### BUGGY CODE ###

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

for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)


for i in range(Q):
    for j,a in enumerate(A):
        if a == B[i]:
            A[j] = C[i]
    print(
        sum(A)
    )


### FIXED CODE ###

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

for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

S = sum(A)
memory = [0] * 100001
for num in A:
    memory[num] += 1

for i in range(Q):
    S_next = S + (C[i] - B[i]) * memory[B[i]]
    print(S_next)
    S = S_next
    memory[C[i]] += memory[B[i]]
    memory[B[i]] = 0
### BUGGY CODE ###

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

check = [[1] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)    

### FIXED CODE ###

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

check = [[1] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,k=map(int, input().split())
    l=list(map(int,input().split()))
    cnt=0
    lans=[]
    for i in range(n-k+1):
        if cnt<sum(l[i:i+k]):
          cnt=sum(l[i:i+k])
          lans=l[i:i+k]
    ans=0
    for j in lans:
        ans+=(0.5*j*(1+j))/j
    print(ans)
resolve()

### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()


def resolve():
    n, k = map(int, input().split())
    from itertools import accumulate
    A = list(map(int, input().split()))
    B = [0] + A
    B = list(accumulate(B))  # 累積和を格納したリスト作成
    num=0
    val=0
    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
    for i in range(k, n + 1):
        if B[i]-B[i-k]>val:
            val=B[i]-B[i-k]
            num=i

    ans = 0
    for j in A[num-k:num]:
        ans += (0.5 * j * (1 + j)) / j
    print(ans)
resolve()
### BUGGY CODE ###

N = int(input())
a = [1,6,36,216,1296,7776,46656]
b = [1,9,81,729,6561,59049]
def ans(n):
  if n<=0:
    return 1000
  elif n in a or n in b:
    return 1
  else:
    return(min(ans(n-1),ans(n-6),ans(n-36),ans(n-216),ans(n-1296),ans(n-7776),ans(n-46656),ans(n-9),ans(n-81),ans(n-729),ans(n-6561),ans(n-59049))+1)
m = 1
while m <= N:
  ans(m)
print(ans(N))
  

### FIXED CODE ###

N = int(input())
def cn(X, n):
    if (int(X/n)):
        return cn(int(X/n), n)+str(X%n)
    return str(X%n)
def su(n):
  ans = 0
  for chara in n:
    ans += int(chara)
  return ans
lis = []
i = 0
while i <= N:
  lis.append(su(cn(i,6))+su(cn(N-i,9)))
  i += 1
print(min(lis))