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

H,W,S= map(int, input().split())
grid=[[v for v in input()] for _ in range(H)]

ans=H*W
for row in range(1<<(H-1)):
    row_cut = str(bin(row))[2:].count("1")
    splits = [grid[0]]
    for i in range(H-1):
        if row & (1<<i):
            splits.append(grid[i+1][:])
        else:
            splits[-1]=[splits[-1][j]+grid[i+1][j] for j in range(W)]

    if any(max(v.count("1") for v in s)>S for s in splits):
        continue

    count=[[] for _ in range(len(splits))]
    for i,s in enumerate(splits):
        for v in s:
            count[i].append(v.count("1"))

    col_cut=0
    tmp_cnt=[count[i][0] for i in range(len(splits))]
    for i in range(1,W):
        merged_cnt=[tmp_cnt[j]+count[j][i] for j in range(len(splits))]
        if max(merged_cnt)>S:
            col_cut+=1
            tmp_cnt =[count[j][i] for j in range(len(splits))]
        else:
            tmp_cnt=merged_cnt
    ans = min(ans,col_cut+row_cut)


print(ans)
    



### FIXED CODE ###

H,W,S= map(int, input().split())
grid=[[v for v in input()] for _ in range(H)]

ans=H*W
for row in range(1<<(H-1)):
    row_cut = str(bin(row))[2:].count("1")
    splits = [grid[0]]
    for i in range(H-1):
        if row & (1<<i):
            splits.append(grid[i+1][:])
        else:
            splits[-1]=[splits[-1][j]+grid[i+1][j] for j in range(W)]

    if any(max(v.count("1") for v in s)>S for s in splits):
        continue

    count=[[] for _ in range(len(splits))]
    for i,s in enumerate(splits):
        for v in s:
            count[i].append(v.count("1"))

    col_cut=0
    tmp_cnt=[count[i][0] for i in range(len(splits))]
    for i in range(1,W):
        merged_cnt=[tmp_cnt[j]+count[j][i] for j in range(len(splits))]
        if max(merged_cnt)>S:
            col_cut+=1
            tmp_cnt =[count[j][i] for j in range(len(splits))]
        else:
            tmp_cnt=merged_cnt
    ans = min(ans,col_cut+row_cut)


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

N, K = map(int, input().split())
h = list(map(int, input().split()))

tmp = [int(1e9)] * (N+10)
for i in range(K):
    if i < len(h):
        tmp[i] = abs(h[i] - h[0])

for i in range(K, N):
    m = int(1e9)
    for j in range(K):
        if i - K >= 0:
            m = min(m, tmp[i-j-1]+abs(h[i]-h[i-j-1]))
            tmp[i] = m


print(tmp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

tmp = [int(1e9)] * (N+10)
for i in range(K):
    if i < len(h):
        tmp[i] = abs(h[i] - h[0])

for i in range(K, N):
    m = int(1e9)
    for j in range(K):
        if i - K >= 0:
            m = min(m, tmp[i-j-1]+abs(h[i]-h[i-j-1]))
            tmp[i] = m


print(tmp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
bond = [[]for _ in range(N)]
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    bond[a].append(b)
    bond[b].append(a)

#qu = [[int(i)for i in input().split()]for _ in range(Q)]
qlis = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    qlis[p-1] += x

que =[]
for i in bond[0]:
    que.append([0,i])
    bond[i].remove(0)

for _ in range(N-1):
    ue,sita = que.pop(0)
    for i in bond[sita]:
        que.append([sita,i])
        bond[i].remove(sita)
    qlis[sita] += qlis[ue]
anstr = " ".join([str(i)for i in qlis])
print(anstr)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
bond = [[]for _ in range(N)]
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    bond[a].append(b)
    bond[b].append(a)

qlis = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    qlis[p-1] += x

stat = [True]*N
stat[0] =False
que =[]
for i in bond[0]:
    que.append([0,i])

for _ in range(N-1):
    ue,sita = que.pop()
    if stat[sita]:
        for i in bond[sita]:
            if stat[i]:
                que.append([sita,i])
        qlis[sita] += qlis[ue]
    stat[sita] = False
anstr = " ".join([str(i)for i in qlis])
print(anstr)
### BUGGY CODE ###

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

sum_a = sum(arr_a)
mod = 10**9 + 7

ans = 0
for i in range(n):
    b = sum(arr_a[i+1:])
    b = b % mod
    ans += arr_a[i] * b
    ans = ans % mod

print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7
memo = {}

for i in range(n):
    if i == 0:
        memo[n-i-1] = 0
    else:
        memo[n-i-1] = (memo[n-i] + arr_a[n-i]) % mod

ans = 0
for i in range(n):
    ans += arr_a[i] * memo[i]
    ans = ans % mod

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

n,k=map(int,input().split())
p=list(map(int,input().split()))
# 連続するK要素を選ぶパターン、n-k+1
mink=min(p[:k])
maxk=max(p[:k])
eq=list(range(n-k+1))
for i in range(n-k+1-1):
  if p[i]==mink and p[i+k]>maxk:
    eq[i+1]=eq[i]
    pass
  if p[i]==mink:
    mink=min(p[i+1:i+k+1])
    maxk=max(maxk,p[i+k])
  if p[i]==maxk:
    mink=min(mink,p[i+k])
    maxk=max(p[i+1:i+k+1])
  else:
    mink=min(mink,p[i+k])
    maxk=max(maxk,p[i+k])

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))
#print(eq)
#print(a)


### FIXED CODE ###

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

#スライド最小値、スライド最大値
from collections import deque
def slide_max_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    max_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] < a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        max_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return max_idx
def slide_min_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    min_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] > a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        min_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return min_idx

min_idx=slide_min_index(p,k+1)
max_idx=slide_max_index(p,k+1)
eq=list(range(n-k+1))
for i in range(n-(k+1)+1):
  if i==min_idx[i+k] and i+k==max_idx[i+k]:
    eq[i+1]=eq[i]

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))
#print(eq)
#print(a)
### BUGGY CODE ###

#!/usr/bin/env python


def main():
    s = input()
    a = []
    for i in range(len(s) + 1):
        lefts, rights = (s[:i], s[i:])
        a_cand = [0, 0]
        j = len(lefts) - 1
        while j >= 0 and lefts[j] == '<':
            a_cand[0] = a_cand[0] + 1
            j = j - 1
        j = 0
        while j < len(rights) and rights[j] == '>':
            a_cand[1] = a_cand[1] + 1
            j = j + 1

        a.append(max(a_cand))

    print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python


def main():
    s = input()
    al, ar = ([0] * (len(s) + 1), [0] * (len(s) + 1))
    for i in range(0, len(s)):
        al[i + 1] = al[i] + 1 if s[i] == '<' else 0

    for i in range(len(s) - 1, -1, -1):
        ar[i] = ar[i + 1] + 1 if s[i] == '>' else 0

    sum_a = sum([max(aln, arn) for aln, arn in zip(al, ar)])
    print(sum_a)


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

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    p25[i] = p25[i - 1] * 25 % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] * inv[n + k - i] * p25[n + k - i] % MOD + MOD) % MOD

print(ans)

### FIXED CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD
    if ans < 0:
        ans += MOD

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

import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=len(set(A))
#print(m,K)
ans=0
if K>=m:
    print(0)
else:
    c = collections.Counter(A)
    for i in range(m-K):
        ans+=c.most_common()[m-1-i][1]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=len(set(A))
ans=0
if K>=m:
    print(0)
else:
    c = collections.Counter(A)
    c_=c.most_common()
    for i in range(m-K):
        ans+=c_[m-1-i][1]
    print(ans)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []

for i in range(M):
    x, y, z = map(int, input().split())
    m.append([x, y, z])

m.sort(key = lambda x: x[2], reverse=True)

for j in m[:min(len(a),len(b))+1]:
    if a[m[0][0]-1] + b[m[0][1]-1] - m[0][2] >= 0 and a[m[0][0]-1] + b[m[0][1]-1] - m[0][2] < min(a) + min(b):
        print(a[m[0][0]-1] + b[m[0][1]-1] - m[0][2])
        exit()

print(min(a) + min(b))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []
am = min(a)
bm = min(b)

for i in range(M):
    x, y, z = map(int, input().split())

    m.append(a[x-1] + b[y-1] - z )



if am + bm > min(m):
    print(min(m))
else:
    print(am + bm)
### BUGGY CODE ###

N = list(map(int, input().split()))
max_num = max(N)

def cal():
  for n in range(max_num):
    n0 = abs(N[0] - n)
    n1 = abs(N[1] - n)
    if n0 == n1:
      return n
  return "IMPOSSIBLE"

print(cal())

### FIXED CODE ###

N = list(map(int, input().split()))
max_num = max(N)

if N[0]%2 != N[1]%2:
  print("IMPOSSIBLE")
else:
  print(int((N[0] + N[1])/2))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
print(*[1+A.index(i) for i in range(1, N+1)])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [[A[i], i+1] for i in range(N)]
B = sorted(B, key=lambda x:x[0])
print(*[B[i][1] for i in range(N)])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().strip().split()]
MOD = 10 ** 9 + 7
ans = 0

for i in range(60+1):
    zero = 0
    one = 0
    m = 1 << i
    for a in A:
        if a & m:
            one += 1
        else:
            zero += 1
    ans += (one * zero) * m
    ans = ans % MOD
print(ans % MOD)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    _ = int(input())
    A = [int(x) for x in input().strip().split()]
    MOD = 10 ** 9 + 7
    ans = 0

    for i in range(60+1):
        zero = 0
        one = 0
        m = 1 << i
        for a in A:
            if a & m:
                one += 1
            else:
                zero += 1
        ans += (one * zero) * m
        ans = ans % MOD
    print(ans % MOD)

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

import numpy as np
import sys

N, K = map(int, input().split())
K2 = K * 2

Mij = np.zeros((K2 + 1, K2 + 1), dtype=int)

diff = [
    [-2, 0],
    [-1, -1],
    [-1, 1],
    [0, 0],
    [1, -1],
    [1, 1],
]


for _ in range(N):
    i, j, s = sys.stdin.readline().split()
    i = int(i) % K2
    j = int(j) % K2
    if s == "B":
        i = (i + K) % K2

    for y, x in diff:
        di = i + y * K
        dj = j + x * K
        i1 = max(di, 0)
        j1 = max(dj, 0)
        i2 = min(di + K, K2)
        j2 = min(dj + K, K2)
        if i1 >= K2 or j1 >= K2 or i2 <= 0 or j2 <= 0:
            continue
        Mij[i1][j1] += 1
        Mij[i2][j1] -= 1
        Mij[i1][j2] -= 1
        Mij[i2][j2] += 1

# 累積和
Mij = np.cumsum(Mij, axis=0)
Mij = np.cumsum(Mij, axis=1)

print(Mij.max())

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
K2 = 2 * K
Mij = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]


def imos(x1, y1, x2, y2):
    Mij[y1][x1] += 1
    Mij[y2][x2] += 1
    Mij[y2][x1] -= 1
    Mij[y1][x2] -= 1

for _ in range(N):
    ls = input().split()
    x = int(ls[0]) % K2
    y = int(ls[1]) % K2
    if ls[2] == "B":
        y = (y + K) % K2
    x_ = x % K
    y_ = y % K

    if (x < K and y < K) or (K <= x and K <= y):
        imos(0, 0, x_ + 1, y_ + 1)
        imos(x_ + K + 1, 0, K2, y_ + 1)
        imos(0, y_ + K + 1, x_ + 1, K2)
        imos(x_ + K + 1, y_ + K + 1, K2, K2)
        imos(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1)
    else:
        imos(x_ + 1, 0, x_ + K + 1, y_ + 1)
        imos(x_ + 1, y_ + K + 1, x_ + K + 1, K2)
        imos(0, y_ + 1, x_ + 1, y_ + K + 1)
        imos(x_ + K + 1, y_ + 1, K2, y_ + K + 1)

Mij = np.array(Mij)
for x in range(K2):
    Mij[:, x + 1] += Mij[:, x]
for y in range(K2):
    Mij[y + 1, :] += Mij[y, :]

print(Mij.max())
### BUGGY CODE ###

#Sから暗証番号Vを作るのではなく、VからSを作れるかを判定する
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for si in range(n):
        if s[si] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Sから暗証番号Vを作るのではなく、VからSを作れるかを判定する
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for si in range(n):
        if s[si] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

K, S = map(int,input().split())

count = 0
for x,y in [(x,y) for x in range(0,K + 1) for y in range(0,K + 1)]:
    z = S - x - y
    if 0 <= z <= K:
        count += 1

print(count)

### FIXED CODE ###

import itertools
    
K, S = map(int,input().split())

count = 0
for x,y in itertools.product(range(0,K + 1),range(0,K + 1)):
    z = S - x - y
    if 0 <= z <= K:
        count += 1

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

import numpy as np

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]
count = 0

for i in range(M):
  B, C = map(int, input().split())
  count = count + B
  for j in range(B):
    A.append(C)

A = np.array(A)
A = np.sort(A)
ans = A[count : len(A)+1]

print(np.sum(ans))


### FIXED CODE ###

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]
BC = [list(map(int, input().split())) for _ in range(M)]
count = 0

BC = sorted(BC, key=lambda x: x[1],reverse=True)
min_A = min(A)

for B,C in BC:
  if min_A >= C and count > N:
    break
  else:
    l = min(B, N-count)
    for i in range(l):
      count+=1
      A.append(C)

A.sort()

ans = sum(A[count:len(A)])

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

import sys
read = sys.stdin.buffer.read

sys.setrecursionlimit(100002)
def myfact(n):
    if n < 2:
        return 1
    else:
        return n * myfact(n - 1)
n,*X=map(int,read().split())
last=X[-1]
X=[last-i for i in X[:-1]]
mod = 10**9+7
f=myfact(n-1)
s = sum(f//i*item for i,item in enumerate(X,1))
print(s%mod)

### FIXED CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


def solve():
    MOD = 10**9 + 7

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

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

n,m=map(int,input().split())
l=m//n
p=1
for i in range(2,l+1):
  if m%i==0:
    if m//i>=n:
      p=i
print(p)

### FIXED CODE ###

n,m=map(int,input().split())
p=1
for i in range(1,int(m**0.5)+1):
  if m%i==0:
    if m//i>=n:
      if i>=n:
        p=max(i,m//i,p)
      else:
        p=max(p,i)
print(p)
### BUGGY CODE ###

import re
rexp = re.compile("AC")
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    print(len(rexp.findall(s)))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == "AC" else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

s = input()
k = int(input())

st = set()
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        st.add(s[i:j])
print(sorted(list(st))[k-1])


### FIXED CODE ###

s = input()
k = int(input())

st = set()
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if j-i<=k: st.add(s[i:j])
print(sorted(list(st))[k-1])
### BUGGY CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
ans = 0
hq = []
for i in range(1, m+1):
    for a, b in ab:
        if a == i:
            heappush(hq, (-b, a))
        
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

ab.sort()
ans = 0
hq = []
idx = 0
for i in range(1, m+1):
    for j in range(idx, n):
        if ab[j][0] == i:
            heappush(hq, (-ab[j][1], ab[j][0]))
            idx += 1
        else:
            break
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for i in range(q)]
if k>q:
    for i in range(n):
        print('Yes')
else:
    for i in range(1,n+1):
        if i not in a:
            print('No')
        else:
            print('Yes' if k-len(a)+a.count(i)>0 else 'No')

### FIXED CODE ###

n,k,q = map(int, input().split())
ans = [0]*n
for i in range(q):
    w = int(input())
    ans[w-1]+=1
for i in range(n):
        print('Yes' if ans[i]>=q-k+1 else 'No')
### BUGGY CODE ###

from collections import deque
n,q=map(int,input().split())
ab=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
px=[tuple(map(int,input().split())) for _ in range(q)]

ans=[0]*(n+1)
for i in range(q):
  ans[px[i][0]]+=px[i][1]
l,m=deque([1]),[]
while l:
  x=l.popleft()
  m.append(x)
  for i in ab[x]:
    if not i in m or i in l:
      l.append(i)
      ans[i]+=ans[x]
      
print(*ans[1:])

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  
  n,q=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  ans=[0]*(n+1)
  for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
  
  l,parent=deque([1]),[0]*(n+1)
  parent[1]=1
  while l:
    x=l.popleft()
    for i in ab[x]:
      if parent[i]:
        continue
      l.append(i)
      ans[i]+=ans[x]
      parent[i]=1
      
  print(*ans[1:])
if __name__=='__main__':
  main()
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
Ap = []
for _ in range(M):
  B,C = map(int,input().split())
  Ap += [C]*B
Ap.sort()
np = len(Ap)
count = 0
i,j = 0,0
while i+j < N:
  a = A[N-i-1]
  b = Ap[np-j-1] if j<np else 0
  if a>=b and i<N:
    count += a
    i += 1
  elif a<b and j<np:
    count += b
    j += 1
print(count)

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
Ap = {}
for _ in range(M):
  B,C = map(int,input().split())
  if C in Ap.keys():
    Ap[C] = Ap[C]+B
  else:
    Ap[C] = B
Clist = sorted(Ap.keys())
nc = len(Clist)
i,j,k = 0,0,0
count = 0
a = A[N-1]
while i+j < N:
  if k<nc:
    c = Clist[nc-k-1]
    b = Ap[c]
  else:b,c = 0,0
  if a>=c:
    count += a
    i += 1
    a = A[N-i-1]
  elif c>a:
    count += b*c if i+j+b<N else c*(N-i-j)
    j += b
    k += 1
print(count)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
# print(a)
# print(n)
ans = [0 for _ in range(n)]


for i_out in range(n):
    for i_in in range(n):  # i_out+1,
        if i_out == i_in:
            continue
        # print(i_out, i_in)
        if int(a[i_in] / a[i_out]) == a[i_in] / a[i_out]:
            ans[i_in] = 1
            # print('!')

# print(ans)
print(n - sum(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
maxa = max(a)
a_s = set(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        for j in range(i, maxa+1, i):
            s.add(j)
        ans += 1

print(ans - len(same_s))
### BUGGY CODE ###

import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Total = 0
count = 0
while count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    break
                elif A[c[0]][c[1]] > A[c[0]][i] + A[c[1]][i]:
                    count = N**2
                    break
        else:
            Total += A[c[0]][c[1]]
                    
if count == N * (N-1) // 2:
    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()