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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = defaultdict(int)
xd = defaultdict(int)
s = [[False]*w for _ in range(h)]
for _ in range(m):
    a,b = inpl()
    yd[a-1] += 1
    xd[b-1] += 1
    s[a-1][b-1] = True
res = 0
for i in range(h):
    for j in range(w):
        tmp = 1 if s[i][j] else 0
        res = max(res, yd[i]+xd[j]-tmp)
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
se = set()
def ind(i,j):
    return i*w + j
for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    se.add((a-1,b-1))
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
# print(yl,xl,res)
for i in yl:
    for j in xl:
        if not (i,j) in se:
            res += 1
            print(res)
            quit()
print(res)
### BUGGY CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
ans = 0

C = list(set(A))
M = len(C)
t = []
for i in range(M):
  t.append(A.count(C[i]))


s = []  
for i in range(M):
  ans = 0
  for j in range(M):
    if i == j:
      p = t[j]-1
    else:
      p = t[j]
    if p >=2:
      ans += math.factorial(p)/(math.factorial(p-2)*2)
  s.append(int(ans))

jisyo = dict(zip(C,s))
#print(jisyo[1])
for i in range(N):
  print(jisyo[A[i]])

### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
ans = 0

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

K, S = map(int, input().split())
res = 0
for X in range(K+1):
    for Y in range(K+1):
        for Z in range(K+1):
            if X+Y+Z == S:
                res += 1
print(res)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np
def main():
    N,W=map(int,input().split())
    dp=np.zeros((N+1,W+1),dtype=int)
    for i in range(1,N+1):
        w,v=map(int,input().split())
        for j in range(W+1):
            if w<=j:
                can1=max(dp[i-1][k] for k in range(j-w+1))
                can2=max(dp[i-1][k] for k in range(j-w+1,j+1))
                dp[i][j]=max(can1+v,can2)
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

def main():
  x, y, a, b, c = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0,
  
  lx = []
  while True:
    if sum([ca, cb, cc]) == x+y:
      break
      
    a = la[0] if len(la) > 0 and ca < x else -1
    b = lb[0] if len(lb) > 0 and cb < y else -1
    c = lc[0] if len(lc) > 0            else -1
            
    if a >= b and a >= c:
      lx.append(a)
      la.pop(0)
      ca += 1
      continue
      
    if b >= a and b >= c:
      lx.append(b)
      lb.pop(0)
      cb += 1
      continue
      
    if c >= b and c >= a:
      lx.append(c)
      lc.pop(0)
      cc += 1
  print(sum(lx))

if __name__=='__main__':
  main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-


def main():
  x, y, na, nb, nc = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0
  
  lx = la[:x] + lb[:y] + lc
  lx.sort(reverse=True)
  print(sum(lx[:x+y]))

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

import itertools

def main():
    n, k = map(int, input().split())

    num = 10*100
    nums = [num + i for i in range(0, n+1)]

    sums = []
    for i in range(k, n+2):
        for v in itertools.combinations(nums, i):
            sums.append(v)

    totals = []
    for s in sums:
        totals.append(sum(s))

    totals = set(totals)
    print(len(totals))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())

    num = 10*100
    nums = [num + i for i in range(0, n+1)]

    # sums = []
    total = 0
    for i in range(k, n+2):
        _min = int((nums[0]+nums[i-1])*(nums[i-1]-nums[0]+1)/2)
        _max = int((nums[-i]+nums[-1])*(nums[-1]-nums[-i]+1)/2)

        total += _max - _min + 1

    print(total%(10**9+7))

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

import math
import itertools
from functools import reduce

def sangcd(i,j,k):
    return reduce(math.gcd, [i,j,k])

K = int(input())
Ans = 0
for i in itertools.product(range(1,K+1), repeat=3):
    Ans += sangcd(i[0],i[1],i[2])

print(Ans)

### FIXED CODE ###

import math
import itertools
from functools import reduce

def sangcd(i,j,k):
    return reduce(math.gcd, [i,j,k])

K = int(input())
Ans = 0
for i in itertools.product(range(1,K+1), repeat=3):
    Ans += sangcd(i[0],i[1],i[2])

print(Ans)
### BUGGY CODE ###


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


for i in range(M):
    B,C = map(int,input().split())
    
    A.extend([C]*B)
b=sorted(A)
print(sum(b[-N:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print(sum(A))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
n = int(input())

tree= [[] for i in range(n+1)]
cost=[[0 for i in range(n+1)]for j in range(n+1)]
color=[0 for i in range(n+1)]
already=[False for i in range(n+1)]
que=[]
for i in range(n-1):
    u,v,w=map(int,input().split(' '))
    tree[u].append(v)
    tree[v].append(u)
    cost[u][v]=w
    cost[v][u]=w
    if(i==n-2):
        que.append(u)
        color[u]=0
        already[u]=True


while(len(que)!=0): 
    node = que.pop()
    for next_node in tree[node]:
        if already[next_node]==False:
            already[next_node]=True
            # print((color[node]+cost[node][next_node])%2)
            color[next_node]=(color[node]+cost[node][next_node])%2
            que.append(next_node)
            
for i in range(1,len(color)):
    print(color[i])


### FIXED CODE ###

# coding: utf-8
# Your code here!
n = int(input())

tree= [[] for i in range(n+1)]
color=[-1 for i in range(n+1)]
que=[]
for i in range(n-1):
    u,v,w=map(int,input().split(' '))
    tree[u].append([v,w])
    tree[v].append([u,w])

que.append(1)
color[1]=0


while(len(que)!=0): 
    node = que.pop()
    for next_node,w in tree[node]:
        if color[next_node]==-1:
            # print((color[node]+cost[node][next_node])%2)
            color[next_node]=(color[node]+w)%2
            que.append(next_node)
            # print(color)
for i in range(1,len(color)):
    print(color[i])
### BUGGY CODE ###

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = tmp1 + B[j]
                if tmp2 < dp[i+A[j]]:
                    dp[i+A[j]] = tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = dijkstra(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

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

import sys
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
tmp=[]
ans=""
for i in range(n-1,-1,-1):
  num = i+1
  total=0
  for j in range(i,n):
    if (j+1)%(i+1)==0:
      total+=b[j]
  if total%2==a[i]:
    b[i]=0
  else:
    b[i]=1
    tmp.append(i+1)

print(sum(b))
tmp = sorted(tmp)

for i in range(len(tmp)):
  ans += str(tmp[i]) + " "
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
tmp=[]
ans=""
for i in range(n-1,-1,-1):
  num = i+1
  total=0
  j=1
  while (i+1)*j <= n:
    total+=b[((i+1)*j)-1]
    j+=1  
  if total%2==a[i]:
    b[i]=0
  else:
    b[i]=1
    tmp.append(i+1)

print(sum(b))
print(str(sorted(tmp)).replace(',','').replace('[','').replace(']',''))
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    num = 0
    while L != R:
        num += abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        L += D
    print(num)

### FIXED CODE ###

from collections import defaultdict
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

d = defaultdict(int)
for i in range(D + 1, H * W + 1):
    d[i] = d[i - D] + abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    print(d[R] - d[L])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
answer = 0
for i in range(len(A)) :
    a = 0
    for j in range(i,len(A)) :
        a = a + A[j]
        if a == 0 :
            answer += 1
print(answer)



### FIXED CODE ###

from math import factorial
N = int(input())
A = list(map(int,input().split()))
L = []
D = {}
ans = 0
L.append(0)
for i in range(len(A)) :
    L.append(L[-1]+A[i])
for j in range(len(L)) :
    if L[j] not in D :
        D[L[j]] = 1
    else :
        D[L[j]] += 1
V = list(D.values())
for k in range(len(V)) :
    if V[k] >= 2 :
        c = factorial(V[k])//(factorial(2)*factorial(V[k]-2))
        ans += c
print(ans)
### BUGGY CODE ###

import math

a,b,n=map(int,input().split())
num=-100
for x in range(1,n+1):
    num=max(num,math.floor(a*x/b)-a*math.floor(x/b))
print(num)



### FIXED CODE ###

import math

a,b,n=map(int,input().split())
num=-100
i=1
if n<b:
    num=max(num,math.floor(a*n/b)-a*math.floor(n/b))
else:
    j=b-1
    num=max(num,math.floor(a*j/b)-a*math.floor(j/b))
print(num)
### BUGGY CODE ###

from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = {}
def opt(l, r, i):
    if i == N: return 0
    T = l, r, i
    if T in DP:
        return DP[T]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, r, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, r-1, i+1)
    DP[T] = max(v1, v2)
    return DP[T]

print(opt(0, N-1, 0))


### FIXED CODE ###

from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = [[-1]*N for _ in range(N)]
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    if DP[i][l] != -1: return DP[i][l]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[i][l] = max(v1, v2)
    return DP[i][l]

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

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

su = sum(array)

def func(c,ar):
    num = max(ar[0:c])
    idx = ar.index(num)
    for i in range(idx+1,c):
        ar[i] = num 
    if idx == 0:
        print(sum(ar)-su)
        return
    func(idx,ar)
    
res = func(N,array)

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
new_array = array
t = sum(array)

for i in range(N-1):
    if array[i] > array[i+1]:
        array[i+1] = array[i]
print(sum(array) - t)
### BUGGY CODE ###

N = int(input())
S = input()


def main():
    ans = 0
    for i in range(1, N):
        S1 = S[:i]
        S2 = S[i:]
        ok = 0
        ng = len(S2) + 1
        k = (ok + ng) // 2
        while ng - ok > 1:
            if S2[:k] in S1:
                ok = k
                k = (k + ng) // 2
            else:
                ng = k
                k = (k + ok) // 2
        ans = max(ans, k)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
base1 = 1007
base2 = 2009

ok = 0
ng = N // 2 + 1
mid = (ok + ng) // 2
while ng - ok > 1:
    seen1 = defaultdict(lambda: 10 ** 5)
    seen2 = defaultdict(lambda: 10 ** 5)
    rh1 = 0
    rh2 = 0
    for i in range(mid):
        rh1 += ord(S[i]) * pow(base1, mid - i - 1, mod1)
        rh2 += ord(S[i]) * pow(base2, mid - i - 1, mod2)
        rh1 %= mod1
        rh2 %= mod2
    seen1[rh1] = 0
    seen2[rh2] = 0
    flag = 0
    for i in range(1, N - mid + 1):
        if flag == 1:
            break
        rh1 = (rh1 * base1 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base1, mid, mod1)) % mod1
        rh2 = (rh2 * base2 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base2, mid, mod2)) % mod2
        if i - seen1[rh1] >= mid and i - seen2[rh2] >= mid:
            ok = mid
            mid = (ok + ng) // 2
            flag = 1
        else:
            if seen1[rh1] == 10 ** 5:
                seen1[rh1] = i
            if seen2[rh2] == 10 ** 5:
                seen2[rh2] = i
    if flag == 0:
        ng = mid
        mid = (ok + ng) // 2

print(ok)
### BUGGY CODE ###

import sys
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF

table = []
for i in range(N):
    d = dijkstra(N, i)
    table.append(d)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    ans = min(ans, t_dis)

print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    #print(each, t_dis)
    ans = min(ans, t_dis)

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

n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
dl = dict()
dr = dict()

for i in range(2**n):
    lr = ""
    rr = ""
    lb = ""
    rb = ""
    ii = i
    for j in range(n):
        if ii&1 == 1:
            lr += ls[j]
            rr += rs[j]
        else:
            lb += ls[j]
            rb += rs[j]
        ii >>= 1
    dl[(lr,lb)] = dl.get((lr,lb),0)+1
    dr[(rr,rb)] = dr.get((rr,rb),0)+1

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*dr.get(dlk,0)

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/agc026/submissions/10971924を参考にした

from collections import defaultdict
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
d = defaultdict(int)

def full_research(sa,r,b,t):
    if t == n:
        d[(r,b)] += 1
        return
    full_research(sa,r+sa[t],b,t+1)
    full_research(sa,r,b+sa[t],t+1)

full_research(ls,"","",0)
dl = d
d = defaultdict(int)
full_research(rs,"","",0)

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*d[dlk]

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] == 1:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] > 0:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

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

res = 0
sorted_lengths = sorted(lengths)
for i in reversed(range(n)):
	l1 = sorted_lengths[i]
	for j in reversed(range(i + 1, n - 1)):
		l2 = sorted_lengths[j]
		rem = sorted_lengths[j + 1:]
		res += bisect_left(rem, l1 + l2) - bisect_left(rem, l1 - l2)

print(res)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		res += bisect_left(lengths, l1 + l2, j + 1) - j - 1

print(res)
### BUGGY CODE ###

import heapq
class pqheap:
    def __init__(self):
        self.p = list()
        self.q = list()

    def insert(self,x):
        heapq.heappush(self.p, x)
        return

    def erase(self,x):
        heapq.heappush(self.q, x)
        return

    def minimum(self):
        while self.q and self.p[0] == self.q[0]:
            heapq.heappop(self.p)
            heapq.heappop(self.q)
        return self.p[0]
n=int(input())
b=list(map(int,input().split()))
a=list(map(int,input().split()))
pq=pqheap()
[pq.insert([-x,i]) for i,x in enumerate(a)]
ans=0
while len(pq.p)>len(pq.q):
    m=pq.minimum()
    pq.erase(m)
    v,i=m
    v=-v
    if v==b[i]:continue
    v-=b[i]    
    tmp=a[(i-1)%n]+a[(i+1)%n]
    if v//tmp==0:
        print(-1)
        exit()
    ans+=v//tmp
    v%=tmp
    v+=b[i]
    a[i]=v
    if v<b[i]:
        print(-1)
        exit()
    pq.insert([-v,i])
print(ans)

"""
3
1 1 1
1000 10000 100000
"""

### FIXED CODE ###

def main(n,a,b):
    ans=0
    while True:
        cnt=0
        for i in range(n):
            m=a[(i-1)%n]+a[(i+1)%n]
            if m<a[i] and b[i]<a[i]:
                a[i]-=b[i]
                cnt+=a[i]//m
                a[i]%=m
                a[i]+=b[i]
        if cnt==0:break
        ans+=cnt
    if a==b:
        print(ans)
    else:
        print(-1)
if __name__=='__main__':
    n=int(input())
    b=list(map(int,input().split()))
    a=list(map(int,input().split()))
    main(n,a,b)