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

strN = '0' + input()

N = int(strN)
numD = len(strN)

dp = [[float('inf')]*(2) for _ in range(numD+1)]
dp[0][0] = 0
for i, Ni in enumerate(reversed(strN), 1):
    Ni = int(Ni)
    if Ni == 9:
        dp[i][0] = dp[i-1][0] + Ni
    else:
        dp[i][0] = min(dp[i-1][0] + Ni, dp[i-1][1] + Ni + 1)
    dp[i][1] = min(dp[i-1][0] + 10 - Ni, dp[i-1][1] + 9 - Ni)

print(dp[numD][0])


### FIXED CODE ###

def solve():
    def min2(x, y): return x if x <= y else y

    strN = '0' + input()

    Ns = list(map(int, strN))

    dp = [0, float('inf')]
    for Ni in reversed(Ns):
        dp2 = [0, 0]
        if Ni == 9:
            dp2[0] = dp[0] + Ni
        else:
            dp2[0] = min2(dp[0] + Ni, dp[1] + Ni + 1)
        dp2[1] = min2(dp[0] + 10 - Ni, dp[1] + 9 - Ni)
        dp = dp2

    print(dp[0])


solve()
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

l = 0
r = n + m + 1
while r - l > 1:
  p = (l + r) // 2
  best = k + 1
  for i in range(p + 1):
    if min(i, n) + min(p - i, m) < p:
      continue
    best = min(best, sum(A[:i]) + sum(B[:p - i]))
  if best <= k:
    l = p
  else:
    r = p
print(l)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

As = [0] * (n + 1)
Bs = [0] * (m + 1)
for i in range(n):
  As[i + 1] = A[i] + As[i]
for i in range(m):
  Bs[i + 1] = B[i] + Bs[i]

l = 0
r = n + m + 1
while r - l > 1:
  p = (l + r) // 2
  best = k + 1
  for i in range(p + 1):
    if min(i, n) + min(p - i, m) < p:
      continue
    best = min(best, As[i] + Bs[p - i])
  if best <= k:
    l = p
  else:
    r = p
print(l)
### BUGGY CODE ###

N = int(input())
memo = {}

def func(i, j):
    if (i, j) in memo:
        return memo[(i, j)]

    count = 0
    for n in range(1, N+1):
        str_n = str(n)
        if str_n[-1] == str(i) and str_n[0] == str(j):
            count += 1
    
    memo[(i,j)] = count
    return count

ret = 0
for i in range(1, N+1):
    ret += func(str(i)[0], str(i)[-1])

print(ret)




### FIXED CODE ###

N = int(input())
memo = {}

def func(i, j):
    if (i, j) in memo:
        return memo[(i, j)]

    count = 0
    n = 1
    while n <= N:
        str_n = str(n)

        if n >= 10 and str_n[0] != str(j):
            n += 10 ** (len(str_n) - 1)
            continue

        if str_n[-1] == str(i) and str_n[0] == str(j):
            count += 1
            n += 10
            continue

        n += 1
    
    memo[(i,j)] = count
    return count

ret = 0
for i in range(1, N+1):
    ret += func(str(i)[0], str(i)[-1])

print(ret)
### BUGGY CODE ###

N = int(input())

def digit_sum(num):
  digit_sum = 0
  while(num > 0):
    digit_sum += num % 10
    num = int(num / 10)
  return digit_sum

min_num = 100000
for A in range(1, N):
  for B in range(1, N):
    if A + B != N:
      continue
    digit_num = digit_sum(A)
    digit_num += digit_sum(B)
    if digit_num < min_num:
      min_num = digit_num

print(min_num)

### FIXED CODE ###

N = int(input())

def digit_sum(num):
  digit_sum = 0
  while(num > 0):
    digit_sum += num % 10
    num = int(num / 10)
  return digit_sum

min_num = 100000
for A in range(1, N):
  B = N - A
  digit_num = digit_sum(A)
  digit_num += digit_sum(B)
  if digit_num < min_num:
    min_num = digit_num

print(min_num)
### BUGGY CODE ###

"""
#include <stdio.h>
int main(){
  int l, r, ans=99999;
  int lst[99999];
  scanf("%d",&l);
  scanf("%d",&r);
  l %= 2019;
  r %= 2019;
  for(int i=l;i<r;i++){
    for(int j=i+1;j<r+1;j++){
      if(ans>(i*j)%2019){
        ans = (i*j)%2019;
        //printf("%d\n",ans);
      }
    }
  }
  printf("%d\n",ans);

}
/*"""
l, r = map(int, input().split())

r -= 2019*(l//2019)
l %= 2019


#lst = []
sum = 9999999999
#lm = 99999999999
#rm = 99999999999
#for 
#print(l%2019)

for i in range(l,r):
  for j in range(i+1,r+1):
    #lst.append(i*j%2019)
    if sum > i*j%2019:
      sum = i*j%2019
print(sum)

#*/

### FIXED CODE ###

l, r = map(int, input().split())
tmp = 2019*(l//2019)
l -= tmp
r -= tmp
if r >= 2019:
  print(0)
else:
  m = 2020
  for i in range(l, r):
    for j in range(i+1, r+1):
      if m > i*j%2019:
        m = i*j%2019
  print(m)
### BUGGY CODE ###

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

for i in range(n):
  a[i] = [(-1) * a[i], (-1) * a[i], 1]

import heapq
heapq.heapify(a)

for _ in range(k):
  i = heapq.heappop(a)
  i[2] += 1
  i[0] = i[1] / i[2]
  heapq.heappush(a, i)

from math import ceil
print(ceil((-1) * heapq.heappop(a)[0]))


### FIXED CODE ###

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

# binary search
left = 1
right = 10 ** 9

while left < right:
    center = (left + right) // 2

    total = 0
    for i in a:
        if i % center == 0:
            i -= 1
        total += i//center
    
    if total > k:
        left = center + 1
    else:
        right = center

print(left)
### BUGGY CODE ###

s = [i for i in input()]
n =len(s)
A=13

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i):
	return a*10**(n-(i+1))%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			

print(dp[n][5]%(10**9+7))
				


### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
import itertools
for a in list(itertools.product([str(b) for b in range(10)], repeat=3)):
  j=0
  for i in range(n):
    if s[i]==a[j]:
      j+=1
      if j==3:
        ans+=1
        break
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
alist=[0]*10
for i in range(n):
  alist[int(s[i])]=i
for i in range(10):
  flag1=False
  for a in range(n-2):
    if s[a]==str(i):
      flag1=True
      break
  if flag1:
    for j in range(10):
      flag2=False
      for b in range(a+1,n-1):
        if s[b]==str(j):
          flag2=True
          break
      if flag2:
        for k in range(10):
          if b<alist[k]:
            ans+=1
print(ans)
### BUGGY CODE ###

s=list(map(int,list(input())))[::-1]

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)

# print(s)
for e,i in enumerate(s):
    D[e]= i*pow(10,e)%2019
# print(D)
c[0] = D[0]
for e,i in enumerate(s):
    if e==0:continue
    c[e] = (c[e-1] + D[e])%2019
# print(c)
ans = 0
f = 0
dp = [0]*(2020)
for e,i in enumerate(c):
    ans +=dp[i]
    dp[i]+=1
print(ans)

### FIXED CODE ###

s=list(map(int,list(input())))[::-1]

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)
ans = 0
f = 0
dp = [0]*(2020)
dp[0]+=1
tmp =0
x = 1
for e,i in enumerate(s):
    tmp = (tmp+x*i)%2019
    ans += dp[tmp]
    dp[tmp]+=1
    x = x*10 %2019
print(ans)
### BUGGY CODE ###

N=int(input())

ans=0
for i in range(1,N+1):
    for j in range(1,N):
        if i <=j:
            continue
        for k in range(1,N):
            if i <=k or i<= k+j:
                continue
            for l in range(1,N):
                if i <=l or i < k+j+l:
                    continue
                if l**2+j**2+k**2+l*j+j*k+k*l==i:
                    ans+=1
    print(ans)
    ans=0

### FIXED CODE ###

N=int(input())

ans=[0]*N

for i in range(1,int(N**0.5)):
    if i**2 >=N:
        break
    for j in range(1,int(N**0.5)):
            if i**2+j**2+i*j>=N:
                break
            for k in range(1,int(N**0.5)):
                    if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                        ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

N,M = map(int,input().split())
for i in range(N,M+1):
    if M%i == 0:
        print(M//i)
        break


### FIXED CODE ###

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

m = M
f = {}
while m%2 == 0:
    f[2] = f.get(2,0) + 1
    m = m//2

k = 3
l = int(m**0.5)+1
while m != 1:
    if k > l:
        f[m] = f.get(m,0)+1
        break
    while m%k == 0:
        f[k] = f.get(k,0)+1
        m = m//k
    k += 2
C=[1]
for k in f:
    C_tmp = []
    for c in C:
        for i in range(f[k]):
            C_tmp.append(c*(k**(i+1)))
    C.extend(C_tmp)
ans_r = M
for c in C:
    if c>=N and c<ans_r:
        ans_r = c
print(M//ans_r)
### BUGGY CODE ###

from collections import Counter
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            app(p)
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 0

for i in range(N):
    for j in range(i + 1, N):
        ans += (A[i] * A[j])
print(ans % mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
su = 0
a = 0

for i in range(N-1,-1,-1):
    su+= A[i] * a
    a += A[i]
print(su % mod)
### BUGGY CODE ###

import itertools
N=int(input())
S=input()
ans=N
for i in range(2, N+1):
  sub=[x for x in list(itertools.combinations(S, i)) if len(x) == len(set(x))]
  ans+=len(sub)
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=1
for c in set(S):
  ans *= (S.count(c)+1)
print((ans-1) % (10**9+7))
### BUGGY CODE ###

def main():
    N=int(input())
    S=input()
    R=[]
    G=[]
    B=[]
    for s in range(N):
        if S[s]=='R':
            R.append(s)
        elif S[s]=='G':
            G.append(s)
        else:
            B.append(s)
    cnt=0
    for r in R:
        for g in G:
            for b in B:
                i=min(min(r,g),b)
                k=max(max(r,g),b)
                j=r+g+b-i-k
                if (j-i)!=(k-j):
                    cnt+=1
    print(cnt)
main()

### FIXED CODE ###

def main():
    N=int(input())
    S=input()
    ans=S.count('R')*S.count('G')*S.count('B')
    for i in range(N):
        for d in range(N):
            j = i+d
            k = j+d
            if k >= N:
                break
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                ans-=1
    print(ans)
main()
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
value = sum(A)
A.append(-1)

cards = M

for i in range(M):
    A = sorted(A,reverse=True)
    p = 0
    while A[p] == max(A) > 0 and cards >= 1:
        A[p] //= 2
        p += 1
        cards -= 1
    if cards == 0 or max(A) == 0:
        break

A.pop()
print(sum(A))

### FIXED CODE ###

import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))

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

x, y, z, k = map(int,input().split())
a =list(map(int,input().split()))
b =list(map(int,input().split()))
c =list(map(int,input().split()))
c.sort(reverse=True)
ab = [0]*(x*y)
l = 0
for i in range(x):
    for j in range(y):
        ab[l] = a[i] + b[j]
        l += 1

ab.sort(reverse=True)
#print(ab)
q = 0
i = 0
j = 0
ans = [0]*(k*k)
l = 0
for i in range(min(k,x*y)):
    for j in range(min(k,z)):
        ans[l] = ab[i] + c[j]
        l += 1

ans.sort(reverse=True)
#print(ans)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x, y, z, k = map(int,input().split())
a =list(map(int,input().split()))
b =list(map(int,input().split()))
c =list(map(int,input().split()))
c.sort(reverse=True)
ab = [0]*(x*y)
l = 0
for i in range(x):
    for j in range(y):
        ab[l] = a[i] + b[j]
        l += 1

ab.sort(reverse=True)
#print(ab)
q = 0
i = 0
j = 0
ans = [0]*(k*k)
l = 0
for i in range(min(k,x*y)):
    for j in range(min(k,z)):
        ans[l] = ab[i] + c[j]
        l += 1

ans.sort(reverse=True)
#print(ans)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
n = input().split()
N = int(n[0])
M = int(n[1])


num_list = []
pr_list = []

for i in range(N):
    a = input().split()
    
    num_list.append(int(a[1]))
    pr_list.append(int(a[0]))

x = np.argsort(np.array(pr_list))

tmp = 0
for i in range(1000):
    if M - np.array(num_list)[x[i]] > 0:
        tmp += int(pr_list[x[i]])*np.array(num_list)[x[i]]
        M -= np.array(num_list)[x[i]]
    elif M - np.array(num_list)[x[i]] < 0:
        tmp += int(pr_list[x[i]])*M
        break
    else:
        if i == 0:
            tmp = int(pr_list[x[i]])*M
            break
        else:
            break

print(str(tmp))



### FIXED CODE ###

import numpy as np
n = input().split()
N = int(n[0])
M = int(n[1])

num_list = []
pr_list = []
for i in range(N):
    a = input().split()
    num_list.append(int(a[1]))
    pr_list.append(int(a[0]))

x = np.argsort(np.array(pr_list))

tmp = 0
for i in range(100000):
    key = int(num_list[x[i]])
    if M - key > 0:
        tmp += int(pr_list[x[i]])*key
        M -= key
    else:
        if i == 0:
            tmp = int(pr_list[x[i]])*M
            break
        tmp += int(pr_list[x[i]])*M
        break

print(str(tmp))
### BUGGY CODE ###

N=int(input())
s=set([])
for i in range(N):
    s=s^{int(input())}
print(len(s))


### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
d={}
for a in A:d[a]=0
for a in A:d[a]+=1
cnt=0
for i in d:
    if d[i]%2:cnt+=1
print(cnt)
### BUGGY CODE ###

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

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
  for k in range(1,K+1):
    if i + k < N:
      dp[i+k] = min(dp[i+k], dp[i] + abs(h[i+k] - h[i]))

print(dp[-1])

### FIXED CODE ###

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

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
  for k in range(1,K+1):
    if i + k < N:
      dp[i+k] = min(dp[i+k], dp[i] + abs(h[i+k] - h[i]))

print(dp[-1])
### BUGGY CODE ###

a, b, c = map(int, input().split())
# print(a ** 0.5, b ** 0.5, c ** 0.5)
digit = 5000
right = (c - a - b) * (10 ** digit)
ab = a * b * (10 ** (digit * 2))
sqrt_ab = 0
ans = False
for i in range(10 ** 5):
    # print(i, i * i * (10 ** (digit * 2)), ab, (i - 1) * (10 ** digit))
    if i * i * (10 ** (digit * 2)) > ab:
        sqrt_ab += (i - 1) * (10 ** digit)
        break
# print(sqrt_ab)
for i in range(1, digit):
    # if int(sqrt_ab + 1) * 2 < right:
    #     ans = True
    #     break
    for j in range(1, 10):
        # print(i, j, sqrt_ab + j * (10 ** (digit - i)), )
        if (sqrt_ab + j * (10 ** (digit - i))) ** 2 > ab:
            sqrt_ab += (j - 1) * (10 ** (digit - i))
            break
        elif j == 9:
            sqrt_ab += j * (10 ** (digit - i))
            break
if 2 * sqrt_ab < right:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if c - a - b > 0 and 4 * a * b < ((c - a - b) ** 2):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

  for j in range(W,-1,-1):
    for i in range(H,-1,-1):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)


print(num_w - Cn[H][W] - 1)







### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)

# print(s,k,n)

ks = {}
m = {}
for i in range(n):
    if s[i] in m.keys():
        m[s[i]] += [i]
    else:
        m[s[i]] = [i]

# "spam".startswith("sp")

m = list(m.items())
# print(m)
m.sort()
# print(m)

# for ky,ixs in m.items():
for ky,ixs in m:
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            c.add(s[i:i+j+1])
            # print(s[i:i+j+1])
    c = list(c)
    c.sort()
    # print(len(c),c)
    # print('---')
    for ans in c:
        k -= 1
        if k == 0:
            print(ans)
            exit()
print(s)


### FIXED CODE ###

s = input()
k = int(input())
n = len(s)

# print('s',s,'k',k)
c = set()
for i in range(n):
    # print(s[i:i+5])
    t = s[i:i+5]
    for j in range(1,5+1):
        # print(t[:j])
        c.add(t[:j])

c = list(c)
c.sort()
# print(*c,sep='\n')
print(c[k-1])
### BUGGY CODE ###

import math

N, C, K = map(int, input().split())
t_dic = {}
for j in range(N):
    t_num = int(input())
    num = t_dic.get(t_num, 0)
    t_dic[t_num] = num + 1

t_list = sorted(t_dic.keys())
removed_man_dic = {}
total_car = 0
for i, t in enumerate(t_list):
    limit = t + K
    limit_num = t_dic[t] - removed_man_dic.get(t, 0)
    if limit_num == 0:
        continue
    car_num = int(math.ceil(limit_num / C))
    total_car += car_num
    passenger = C * car_num
    remaining_seat = passenger - limit_num
    removed_man_dic = {}
    for j in t_list[i+1:]:
        if j >= limit:
            break
        num = t_dic.get(j, 0)
        if num <= remaining_seat:
            remaining_seat -= num
            removed_man_dic[j] = num
        else:
            removed_man_dic[j] = remaining_seat
            break

print(total_car)


### FIXED CODE ###

N, C, K = map(int, input().split())
t_sorted = [int(input()) for _ in range(N)]
t_sorted.sort()

car = 0
passenger = 0
target_t, limit = 0, 0
for i, t in enumerate(t_sorted):
    if target_t == 0:
        target_t = t
        limit = t + K
    passenger += 1
    if passenger == C:
        car += 1
        passenger = 0
        target_t = 0
        continue
    if i != N - 1:
        if t_sorted[i + 1] > limit:
            car += 1
            passenger = 0
            target_t = 0
            continue
if passenger > 0:
    car += 1

print(car)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort(reverse=True)
for _ in range(min(k,n)):
    h.pop(0)
print(sum(h))

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort(reverse=True)
# for _ in range(min(k,n)):
#     h.pop(0)
print(sum(h[min(k,n):]))
### BUGGY CODE ###

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

for i in range(M):
    Bi, Ci = map(int, input().split())
    for j in range(Bi):
        if A[j] < Ci:
            A[j] = Ci
    A = sorted(A)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = map(int, input().split())
card = {}
for a in A:
    if a not in card:
        card[a] = 1
    else:
        card[a] += 1

for i in range(M):
    Bi, Ci = map(int, input().split())
    if Ci not in card:
        card[Ci] = Bi
    else:
        card[Ci] += Bi

total = 0
count = 0
for num in sorted(card.keys(), reverse=True):
    if count + card[num] <= N:
        count += card[num]
        total += num * card[num]
    else:
        added = N - count
        count += added
        total += added * num
        break
print(total)
### BUGGY CODE ###

import sys,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    if b[i] != a[i]:
        hq.heappush(t,(-b[i],i))
co = 0
while t:
    k = hq.heappop(t)
    k = (-k[0],k[1])
    q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
    co += q
    if q == 0:
        print(-1)
        exit()
    w = a[k[1]] + w
    b[k[1]] = w
    if b[k[1]] != a[k[1]]:
        hq.heappush(t,(-w,k[1]))

print(co)


### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())