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

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[0 for i in range(n)]
for i in range(n):
	uselist[i]=lists[i]//2           
import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)

### FIXED CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[]
for some in lists:
    some=some//2
    uselist.append(some)

import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

S = sorted(S)

v = S[0]
c = 0
for i in range(N):
    if v == S[i]:
        c +=1
    else:
        break
del S[0:c]
N = N -c
L = [[v,c]]

while S != []:
    v = S[0]
    c = 0
    for i in range(N):
        if v == S[i]:
            c +=1
        else:
            break
    del S[0:c]
    N = N-c
    if L[0][1] == c:
        L.append([v,c])
    elif L[0][1] < c:
        L = [[v,c]]

for l in L:
    print(l[0])

### FIXED CODE ###

N = int(input())

L = {}

for i in range(N):
    s = input()
    if s in L.keys():
        L[s] +=1
    else:
        L[s] = 1

L = sorted(L.items(),key=lambda x:x[1],reverse=True)

S = []
c = L[0][1]
for i in range(len(L)):
    if c == L[i][1]:
        S.append(L[i][0])
    else:
        break
S = sorted(S)
for s in S:
    print(s)
### BUGGY CODE ###

s =  [0] + [ord(i) for i in input()]

ret = 0
i = 0

while i < len(s) :
    if s[i:i+3] == [65, 66, 67] :
        s[i:i+3] = [66, 67, 65]
        ret += 1
        i -= 1
    else :
        i += 1

print(ret)

### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

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

from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
dli = [[] for _ in range(D)]
for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        dli[j%D].append([j,i,ind])
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = []
dinds = []
for d in dli:
    #total dist,now pos
    #inds = num
    stim = [[0,0,0]]
    inds = []
    d.sort(key=itemgetter(0))
    for i in d:
        stim.append([stim[-1][0]+abs(i[1]-stim[-1][1])+abs(i[2]-stim[-1][2]),i[1],i[2]])
        inds.append(i[0])
    stims.append(stim)
    dinds.append(inds)

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum].index(i[0])+1
    r = dinds[dnum].index(i[1])+1
    print(stims[dnum][r][0]-stims[dnum][l][0])


### FIXED CODE ###

from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
a = []

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = [[[0,0,0]]for _ in range(D)]
dinds = [{}for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d][i[0]]=len(stims[d])-1

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum][i[0]]
    r = dinds[dnum][i[1]]
    print(stims[dnum][r][0]-stims[dnum][l][0])
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i  in input().split()]
#Aについても、修行前の大小で並べてしまって良いです
A=np.array(sorted(a))
F=np.array(sorted(f, reverse=True))
#最大値の最小化▶︎二分探索！
#答えxを決めて、A*Fペア全てをx以下にするために必要な修行がk回以下かを調べていく。(xについて二分探索)
left=-1
right=10**12
s=A.sum()
x=(left+right)//2
#A-x//Fは、x以下にするのに必要な最小の修行回数。
#np.maximum(A-x//F,0)は、２つの配列の大きい方を取っていきながらあたらしい配列を作っている。
while left+1<right:
    if np.maximum(A-x//F,0).sum()<=k:
        #この時答えはx以下なので
        right=x
    else:
        #この時答えはxより大きいので
        left=x
print(right)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i  in input().split()]
#Aについても、修行前の大小で並べてしまって良いです
A=np.array(sorted(a))
F=np.array(sorted(f, reverse=True))
#最大値の最小化▶︎二分探索！
#答えxを決めて、A*Fペア全てをx以下にするために必要な修行がk回以下かを調べていく。(xについて二分探索)
left=-1
right=10**12
s=A.sum()
#A-x//Fは、x以下にするのに必要な最小の修行回数。
#np.maximum(A-x//F,0)は、２つの配列の大きい方を取っていきながらあたらしい配列を作っている。
while left+1<right:
    x=(left+right)//2
    if np.maximum(A-x//F , 0).sum()<=k:
        #この時答えはx以下なので
        right=x
    else:
        #この時答えはxより大きいので
        left=x
print(right)
### BUGGY CODE ###

def resolve():
    k, s = map(int, input().split())
    cnt = 0
    k += 1
    for i in range(k):
        if i > s:
            break
        for j in range(k):
            if i+j > s:
                break
            for l in range(k):
                if i+j+l == s:
                    cnt += 1
                elif i+j+l > s:
                    break
    print(cnt)
resolve()

### FIXED CODE ###

def resolve():
    k, s = map(int, input().split())
    cnt = 0
    for i in range(k+1):
        if i > s:
            break
        for j in range(k+1):
            if 0 <= s-i-j <= k:
                cnt += 1
            elif s-i-j < 0:
                break
    print(cnt)
resolve()
### BUGGY CODE ###

s = input()

n = int(s)

x = 1

for num in range(n):
    x *= num + 1

answer = x % ((1000000000) + 7)

print(answer)

### FIXED CODE ###

s = input()

n = int(s)

x = 1

for num in range(n):
    x *= num + 1
    x = x % ((1000000000) + 7)



print(x)
### BUGGY CODE ###

N = int(input())
lst = []
count = 0
for _ in range(N):
    s = input()
    if not s in lst:
        lst.append(s)
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = set()
count = 0
for _ in range(N):
    s = input()
    S.add(s)
print(len(S))
### BUGGY CODE ###

from collections import deque

n,m=map(int,input().split())
l=set(map(int,input().split()))
l=[i/2 for i in l]

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

if len(l)==1:
  lcm=l.pop()
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))
  exit()
  
lcm=1
for a in l:
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  
if lcm>m:
  print(0)
  exit()
  
for a in l:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))


### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

def lcm(a,b):
    g=math.gcd(a,b)
    return b*(a//g)
l=a[0]//2
for i in range(n):
    r=a[i]//2
    l=lcm(l,r)
for i in range(n):
    if (l//(a[i]//2))%2==0:
        print(0)
        exit()
res=m//l
print((res+1)//2)
### BUGGY CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [0] * n ** 2

    def f(i, j):
        return i * n + j

    for i in range(n):
        dp[f(i, i)] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[f(i + 1, j)]
            R = a[j] - dp[f(i, j - 1)]
            if L > R:
                dp[f(i, j)] = L
            else:
                dp[f(i, j)] = R
    return dp[f(0, n - 1)]


print(solve())


### FIXED CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())
### BUGGY CODE ###

#c
import sys
#再起の上限を増やす
sys.setrecursionlimit(10 ** 7)

N = int(input())
H = list(map(int, input().split()))
cnt=0
ans=0
now=0
def func(now,N,H,cnt,ans):
    for i in range(now,N-1):
        if H[i]>=H[i+1]:
            cnt+=1
            if cnt>ans:
                ans=cnt
        else:
            cnt=0
            func(i+1,N,H,cnt,ans)
    return ans
            
print(func(now,N,H,cnt,ans))

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
cnt=0
ans=0
now=0
for i in range(now,N-1):
    if H[i]>=H[i+1]:
        cnt+=1
        if cnt>ans:
            ans=cnt
    else:
        cnt=0

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

NK = list(map(int, input().split(' ')))
N = NK[0]
K = NK[1]
A = list(map(int, input().split(' ')))

score = A[0]
for i in range(1, K):
    score = score * A[i]
score_list = [score]

for i in range(K, N):
    score = score * A[i] / A[i-K]
    score_list.append(score)

for i in range(len(score_list) - 1):
    if (score_list[i] < score_list[i+1]):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

NK = list(map(int, input().split(' ')))
N = NK[0]
K = NK[1]
A = list(map(int, input().split(' ')))

for i in range(K, N):
    if (A[i-K] < A[i]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
MOD = 998244353  # type: int

def solve(N: int, S: int, A: "List[int]"):
    dp = [[0]*(S+1) for _ in range(N+1)]

    for i in range(N):
        for s in range(S+1):
            if s >= A[i]:
                dp[i+1][s] = dp[i][s]+dp[i][s-A[i]]+int(A[i]==s or s==0)
            else:
                dp[i+1][s] = dp[i][s]+int(A[i]==s or s==0)
            dp[i+1][s]%=MOD
    
    answer = 0
    for i in range(N):
        answer += dp[i+1][S]
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 998244353  # type: int

def solve(N: int, S: int, A: "List[int]"):
    dp = [[0]*(S+1) for _ in range(N+1)]

    for i in range(N):
        for s in range(S+1):
            if s >= A[i]:
                dp[i+1][s] = dp[i][s]+dp[i][s-A[i]]+int(A[i]==s or s==0)
            else:
                dp[i+1][s] = dp[i][s]+int(A[i]==s or s==0)
            dp[i+1][s]%=MOD
    
    answer = 0
    for i in range(N):
        answer += dp[i+1][S]
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)

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

_MAXN = 8000

s = list( input() )
x,y = map( int, input().split() )

move_cnt = 0
change_cnt = 0
x_move = []
y_move = []
for i in range(len(s)):
    if s[i] == 'F':
        move_cnt += 1
    else:
        if change_cnt % 2 == 0:
            x_move.append(move_cnt)
        else:
            y_move.append(move_cnt)
        change_cnt += 1
        move_cnt = 0
if change_cnt % 2 == 0:
    x_move.append(move_cnt)
else:
    y_move.append(move_cnt)

x_dp = [[False]*_MAXN*2 for i in range(_MAXN//2+1)]
y_dp = [[False]*_MAXN*2 for i in range(_MAXN//2+1)]
x_dp[0][0] = True
y_dp[0][0] = True

for i in range(len(x_move)):
    for j in range(-_MAXN,_MAXN):
        if x_dp[i][j] == True:
            if j - x_move[i] > -_MAXN:
                x_dp[i+1][j-x_move[i]] = True
            if j + x_move[i] < _MAXN:
                x_dp[i+1][j+x_move[i]] = True

for i in range(len(y_move)):
    for j in range(-_MAXN,_MAXN):
        if y_dp[i][j] == True:
            if j - y_move[i] > -_MAXN:
                y_dp[i+1][j-y_move[i]] = True
            if j + y_move[i] < _MAXN:
                y_dp[i+1][j+y_move[i]] = True

if x_dp[len(x_move)][x] and y_dp[len(y_move)][y]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

def isReach( goal, move, is_x):
    msum = sum(move)
    m = len(move)

    if msum < abs(goal):
        return False

    dp = [[False for _ in range(msum*2+1)] for _ in range(m+1)]
    dp[0][0] = True
    
    for i in range(m):
        for j in range(-msum,msum+1):
            if i == 0 and dp[i][j] and is_x:
                dp[i+1][j+move[i]] = True
            elif dp[i][j]:
                dp[i+1][j-move[i]] = True
                dp[i+1][j+move[i]] = True
    
    return dp[m][goal]


s = list( input().split('T') )
x,y = map( int, input().split() )

move_dist = [len(move) for move in s]
x_move = move_dist[0::2]
y_move = move_dist[1::2]

if isReach(x,x_move,True) and isReach(y,y_move,False):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    cnt = 0
    for i in range(n):
        l = (i + 1) + a[i]
        for j in range(n):
            r = (j + 1) - a[j]
            if l == r:
                cnt += 1
        



    
    return cnt




print(solve())


### FIXED CODE ###

from collections import*
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    l = []
    r = []
    for i, j in enumerate(a):
        l += [i + j]
        r += [i - j]

    cnt = 0
    l = Counter(l)
    for r in r:
        cnt += l.get(r, 0)

    
    return cnt




print(solve())
### BUGGY CODE ###

n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=[]
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde+=[lista[i]]
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde+=[lista[i]]
print(s)
    
        


### FIXED CODE ###

n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    
    if(listtf[lista[i]-1]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<=lista[n-1]):
            listtf[lista[i]*t-1]=False
            t+=1
print(s)
### BUGGY CODE ###

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

a = 0
sum_A = {}

for g in range(N):
	a += A[g]
	amari = a%M
	if amari in sum_A.keys():
		sum_A[amari] += 1
	else:
		sum_A[amari] = 1

if sum_A.get(0)!=None:
	ans = sum_A[0]
else:
	ans = 0
for l in range(len(sum_A)):
	if sum_A[list(sum_A)[l]] >= 2:
		ans += (sum_A[list(sum_A)[l]]-1)*sum_A[list(sum_A)[l]]/2
print(int(ans))

### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate

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

acc=list(accumulate(A))

d=defaultdict(int)

ans=0
for i in range(N):
    if acc[i]%M==0:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]
    else:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]-1
print(ans)
### BUGGY CODE ###


h,w=map(int,input().split())
s=[[]*w for i in range(h)]
for i in range(h):
    s[i]=list(input())

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                for jj in range(jst,jed+1):
                    ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            if isum!=0:
                for ii in range(ist,ied+1):
                    hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)
             

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    si=input()
    s[i]=si
"""
h,w=4,6
s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    
"""
ww=[[0]*w for i in range(h)]
#www=[[0]*w for i in range(h)]
www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*(w+1)
    for j in range(w):
        if s[i][j]==".":
#            www[i][j]=jcnt
            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="#":
                jcnt+=1
            jsum+=1
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            ww[i][j]=jj[www[j]]
#    print(jj)
                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*(h+1)
    for i in range(h):
        if s[i][j]==".":
#            www[i][j]=jcnt
            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="#":
                icnt+=1
            isum+=1
        else:
#            print(jsum,jst,jed)
            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            hh[i][j]=ii[hhh[i]]
#    print(jj)
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)
### BUGGY CODE ###

c=input("").split(" ")
a=int(c[0])
if(a>10000000000000):
  while(True):
    None
e=100*int(c[1][0])+10*int(c[1][2])+int(c[1][3])

d=a*e
ff=d%100
d-=ff
print(int(d/100))

### FIXED CODE ###

c=input("").split(" ")
a=int(c[0])

e=100*int(c[1][0])+10*int(c[1][2])+int(c[1][3])

d=int(a*e)
s=str(d)
if (len(s)<3):
    f="0"
else:
    f=s[:len(s)-2]

print(f)
### BUGGY CODE ###

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

c = N - K + 1
dp = [0 for _ in range(c)]

for i in range(c):
    dp[i] = sum(P[i:i + K])

n = dp.index(max(dp))

pp = sum(map(lambda x: sum(range(1, int(x) + 1)) / x, P[n: n + K]))

print('{:.10f}'.format(pp))


### FIXED CODE ###

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

p = [0]
for i in range(N):
    p.append(p[-1] + (P[i] + 1) / 2)

print(max(p[i+K] - p[i] for i in range(N-K+1)))
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ma=max(A)
import heapq
BB=[]
Chk=[False]*n
for i in range(n):
  if A[i]==B[i]:
    Chk[i]=True
for i in range(n):
  BB.append([-B[i],i])
heapq.heapify(BB)
ans=0
while BB:
  b,ind=heapq.heappop(BB)
  if Chk[ind]:
    continue
  else:
    if ind==0:
      d=B[-1]+B[1]
      b_next=max(B[-1],B[1])
    elif ind==n-1:
      d=B[-2]+B[0]
      b_next=max(B[-2],B[0])
    else:
      d=B[ind-1]+B[ind+1]
      b_next=max(B[ind-1],B[ind+1])
    b_next=max(b_next,A[ind])
    ans+=(-b-b_next-1)//d+1
    b+=d*((-b-b_next-1)//d+1)
    B[ind]=-b
    if b>0:
      break
    elif A[ind]==-b:
      Chk[ind]=True
    else:
      heapq.heappush(BB,[b,ind])
  
print(ans if A==B else -1)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2, N):
        k = 1
        while i - k > 0 or K >= k:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))
            k += 1

    print(dp[-1])


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2, N):
        k = 1
        for k in range(1, K + 1):
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))
    print(dp[-1])


main()
### BUGGY CODE ###

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)

lis[0].reverse()

for i in lis[-1]:
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

import itertools

s = list(str(input()))
t = list(str(input()))
s_all = ["".join(i) for i in itertools.permutations(s)]
t_all = ["".join(j) for j in itertools.permutations(t)]

for k in s_all:
    for l in t_all:
        if k < l:
            print("Yes")
            quit(0)
        else:
            continue

print("No")


### FIXED CODE ###

s = "".join(sorted(input()))
t = "".join(sorted((input()))[::-1])
if s < t:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

ans = 1

exit
for i in a:
    ans *= i

if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()
        
print(ans)
### BUGGY CODE ###

N = int(input())
a = []
b = []
for _ in range(N):
    ai,bi = list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
ans = 0
for i in range(N-1,-1,-1):
    t = (b[i] - a[i] ) % b[i]
    a[:i] = map(lambda x:x+t,a[:i])
    ans += t
print(ans)

### FIXED CODE ###

N = int(input())
a = []
b = []
for _ in range(N):
    ai,bi = list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
ans = 0
for i in range(N-1,-1,-1):
    a[i] += ans
    t = (b[i] - a[i] ) % b[i]
    ans += t
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]* N
dp[0] = 0
for j in range(1, N):
    for i in range(max(0, j-K), j):
        dp[j] = min(dp[i]+abs(h[j]-h[i]), dp[j])
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 j in range(1, N):
    for i in range(max(0, j-K), j):
        dp[j] = min(dp[i]+abs(h[j]-h[i]), dp[j])
print(dp[-1])