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


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

D = []

for i in range(C):

    d = list(map(int,input().split()))

    D.append(d)

c = []

for i in range(N):

    cc = list(map(int,input().split()))
    c.append(cc)


lis1 = []
lis2 = []
lis3 = []

for c1 in range(C):

    c1 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 0 and c[i][j] != c1:

                now += D[c[i][j]-1][c1-1]

    lis1.append(now)


for c2 in range(C):

    c2 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 1 and c[i][j] != c2:

                now += D[c[i][j]-1][c2-1]

    lis2.append(now)


for c3 in range(C):

    c3 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 2 and c[i][j] != c3:

                now += D[c[i][j]-1][c3-1]

    lis3.append(now)


ans = float("inf")

for i in range(C):

    for j in range(C):

        for k in range(C):


            if i == j or j == k or k == i :
                continue;

            ans = min(ans,lis1[i] + lis2[j] + lis3[k])

print (ans)

    

### FIXED CODE ###


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

D = []

for i in range(C):

    d = list(map(int,input().split()))

    D.append(d)

c = []

for i in range(N):

    cc = list(map(int,input().split()))
    c.append(cc)


lis1 = []
lis2 = []
lis3 = []

for c1 in range(C):

    c1 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 0 and c[i][j] != c1:

                now += D[c[i][j]-1][c1-1]

    lis1.append(now)


for c2 in range(C):

    c2 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 1 and c[i][j] != c2:

                now += D[c[i][j]-1][c2-1]

    lis2.append(now)


for c3 in range(C):

    c3 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 2 and c[i][j] != c3:

                now += D[c[i][j]-1][c3-1]

    lis3.append(now)


ans = float("inf")

for i in range(C):

    for j in range(C):

        for k in range(C):


            if i == j or j == k or k == i :
                continue;

            ans = min(ans,lis1[i] + lis2[j] + lis3[k])

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

K=list()
L=list()
N=int(input())
R=[0]*N
for i in range(N):
  A=input()
  if A in L:
    R[L.index(A)]+=1
    L.append(A)
  else:
    R[i]+=1
    L.append(A)
c=max(R)
for i in range(N):
  if R[i]==c:
    K.append(L[i])
K=sorted(K)
for i in range(len(K)):
  print(K[i])

### FIXED CODE ###

c={}
N=int(input())
for i in range(N):
  s=input()
  if s not in c:
    c[s]=1
  else:
    c[s]+=1
n=max(c.values())
L=list()
for i in c:
  if c[i]==n:
    L.append(i)
L=sorted(L)
for i in L:
  print(i)
### BUGGY CODE ###

import sys

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

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
        gaps = sorted(gap)

print(sum(gaps[:m-n]))


### FIXED CODE ###

import sys

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

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
    gaps = sorted(gap)

print(sum(gaps[:m-n]))
### BUGGY CODE ###

q=int(input())

#prime table
prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

for i in range(q):
  l,r=map(int,input().split())
  cnt=0
  for j in range(l,r+1,2):
    if prime[j]==j and prime[(j+1)//2]==(j+1)//2:
      cnt+=1
  print(cnt)



### FIXED CODE ###

q=int(input())

#prime table
prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

like2017=[0 for i in range(10**5+5)]
for i in range(3,10**5+5,2):
  j=(i+1)//2
  if i==prime[i] and j==prime[j]:
    like2017[i]=1

like2017sum=[0 for i in range(10**5+5)]
for i in range(10**5+4):
  like2017sum[i+1]=like2017sum[i]+like2017[i+1]
#print(like2017[0:54])
#print(like2017sum[0:80])
for i in range(q):
  l,r=map(int,input().split())
  if like2017[l]==1:
    alpha=1
  else:
    alpha=0
  print(like2017sum[r]-like2017sum[l]+alpha)
### BUGGY CODE ###

N=int(input())
total=1
flag=True
A=list(map(int,input().split()))

for i in A:
  total*=i
  
if 1*(10**18)+1<=total:
  print("-1")
else:
  print(total)

### FIXED CODE ###

N=int(input())
total=1
A=list(map(int,input().split()))
flag=True
high=1*(10**18)+1
if A.count(0)>=1:
  total=0
else:
  for i in range(N):
    total*=A[i]
    if high<=total:
      flag=False
      break

if not flag:
  print("-1")
else:
  print(total)
### BUGGY CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = A

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
               # if d[i][j] == d[i][k] + d[k][j]:
               #   if (i != k) and (j != k):
               #     ans += d[i][j]
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################

#d = [[float("inf") for i in range(10)] for i in range(10)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
#for i in range(10):
#  for j in range(10):
#    d[i][j] = C[i][j]

#print(warshall_floyd(d))
#print(warshall_floyd(C))
B = copy.deepcopy(A)
cost = warshall_floyd(B)
#print(cost , A)

ans = 0
for i in range(N):
  for j in range(N):
    if cost[i][j] < A[i][j]:
      print("-1")
      quit()

for i in range(N):
  cost[i][i] = 10 ** 18
for i in range(N):
  for j in range(N):
    p = 1
    for k in range(N):
      if cost[i][j] >= cost[i][k] + cost[k][j]:
        p = 0
        break
    if p == 1:
      ans += cost[i][j]


ans = ans / 2
#for i in range(10):
#  ans += num[i] * cost[i][1]

print(int(ans))

### FIXED CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = A

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
               # if d[i][j] == d[i][k] + d[k][j]:
               #   if (i != k) and (j != k):
               #     ans += d[i][j]
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################

#d = [[float("inf") for i in range(10)] for i in range(10)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
#for i in range(10):
#  for j in range(10):
#    d[i][j] = C[i][j]

#print(warshall_floyd(d))
#print(warshall_floyd(C))
B = copy.deepcopy(A)
cost = warshall_floyd(B)
#print(cost , A)

ans = 0
for i in range(N):
  for j in range(N):
    if cost[i][j] < A[i][j]:
      print("-1")
      quit()

for i in range(N):
  cost[i][i] = 10 ** 18
for i in range(N):
  for j in range(N):
    p = 1
    for k in range(N):
      if cost[i][j] >= cost[i][k] + cost[k][j]:
        p = 0
        break
    if p == 1:
      ans += cost[i][j]


ans = ans / 2
#for i in range(10):
#  ans += num[i] * cost[i][1]

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

a,b = map(int, input().split())

if b == 1:
    print(0)
    exit()
      
while True:
    x = abs(a-b)
    if x < a:
        a = x
    else:
        print(a)
        break

### FIXED CODE ###

a,b = map(int, input().split())

if a > b:
    if a % b == 0:
        print(0)
        exit()
    else:
        print(min(a%b, b-(a%b)))
        exit()

while True:
    x = abs(a-b)
    if x < a:
        a = x
    else:
        print(a)
        break
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
m+='@'*w,
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

n=int(input())
L=[int(x) for x in input().split()]
sum=0
mod=1000000007
for i in range(n-1):
    for j in range(i+1,n):
        sum+=(L[i]*L[j])%mod
print(sum%mod)


### FIXED CODE ###

n=int(input())
L=[int(x) for x in input().split()]
sum=0
product=0
mod=1000000007
for i in range(n):
    sum+=L[i]%mod
for i in range(n-1):
    sum-=(L[i]%mod)
    product+=sum*(L[i]%mod)
print(product%mod)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
  
keta=[0]*60
for i in range(n):
  tar=A[i]
  ind=0
  while tar>0:
    if tar&1==1:
      keta[ind]+=1
    tar>>=1
    ind+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
binA=[None]*n
for i in range(n):
  binA[i]=bin(A[i])[2:]
  
keta=[0]*60
for i in range(n):
  tar=binA[i]
  for j in range(len(tar)-1,-1,-1):
    if tar[j]=="1":
      keta[len(tar)-1-j]+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

x=np.array(x)
y=np.array(y)
z=np.vstack((x,y))
zz=np.argsort(z[1,:])[::-1]
z=z[:,zz]


left=z[1,0]
flag='Yes'
for i in range(N):
  
  if min(left,z[1,i])<sum(z[0,i:]):
    flag='No'

    break
  else:
    left=z[1,i]-z[0,i]
print(flag)

### FIXED CODE ###

import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

x=np.array(x)
y=np.array(y)
z=np.vstack((x,y))
zz=np.argsort(z[1,:])[::-1]
z=z[:,zz]

left=z[1,0]
flag='Yes'
sumarray=np.cumsum(z[0][::-1])[::-1]
for i in range(N):
  
  if min(left,z[1,i])<sumarray[i]:
    flag='No'
    break
  else:
    left=z[1,i]-z[0,i]
print(flag)
### BUGGY CODE ###

from collections import Counter
N = int(input())

A = list(map(int, input().split()))
c = Counter(A)
s = c.most_common()[0][0]
idx_s = [i for i,x in enumerate(A) if x == s]
l = idx_s[0]
r = idx_s[1]

def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret

for i in range(1,N+2):
    print((nCr(N+1, i) - nCr(l+N+1-(r+1), i-1)) % (10**9+7))

### FIXED CODE ###

from collections import Counter
N = int(input())

A = list(map(int, input().split()))
c = Counter(A)
s = c.most_common()[0][0]
idx_s = [i for i,x in enumerate(A) if x == s]
l = idx_s[0]
r = idx_s[1]

MOD = 10**9+7
fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

for i in range(1,N+2):
    print((nCr(N+1, i) - nCr(l+N+1-(r+1), i-1)) % MOD)
### BUGGY CODE ###

# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if not((i,j) in d_a) and ((i,j) != (0,0)):
            d_b += [(i,j)]

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

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(len(dist)):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(len(dist[0])):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        di, dj = d_b[v][0]+i, d_b[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

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

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:\n
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    # 到着する町の計算
    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)
### BUGGY CODE ###

def main():
    import collections
    N, P = map(int, input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        D = [0] * N
        A = [0] * (N + 1)
        for i, s in enumerate(S):
            D[i] = int(s) * 10 ** i % P
            if i == 0:
                A[i] = D[i]
            else:
                A[i] = (D[i] + A[i - 1]) % P
        c = collections.Counter(A)
        ans = sum([i * (i - 1) // 2 for i in c.values()])
    
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import collections
    N, P = map(int, input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mod = [0] * P
        mod[0] = 1
        current = 0
        X = 1
        for s in S:
            current = (current + int(s) * X) % P
            ans += mod[current]
            mod[current] += 1
            X = X * 10 % P
    
    print(ans)

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

import collections
N, M = map(int, input().split())
graph = collections.defaultdict(lambda:set())
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)
    graph[b-1].add(a-1)

def bfs(v, goal, graph, seen, next_v, rank):
    for x in graph[v]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)
    return False


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(next_v[0], N-1, graph, seen, next_v, rank):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
    rank.pop(0)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for _ in range(N)] 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)
### BUGGY CODE ###

def test():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
    
    for i in range(1,N):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K, 0), i))
    
    print(dp[N-1])
    
if __name__ == '__main__':
    test()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if (ax[0] + cnt) % bx[0] !=0:
        k = bx[0] - ((ax[0] + cnt) % bx[0])
        cnt += k
        ax.pop(0)
        bx.pop(0)
print cnt


### FIXED CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if (ax[i] + cnt) % bx[i] !=0:
        k = bx[i] - ((ax[i] + cnt) % bx[i])
        cnt += k

print cnt
### BUGGY CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)
    cnt = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        done = [0] * W
        for j in range(W):
            if G[i][j] == "#":
                continue
            if done[j]:
                continue
            length = 0
            while j + length < W:
                if G[i][j+length] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i][j + k] += length
                done[j + k] = 1

    for j in range(W):
        done = [0] * H
        for i in range(H):
            if G[i][j] == "#":
                continue
            if done[i]:
                continue
            length = 0
            while i + length < H:
                if G[i+length][j] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i + k][j] += length
                done[i + k] = 1
    ans = 0
    for i in range(H):
        ans = max(ans, max(cnt[i]) - 1)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)
    cnt = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        done = [0] * W
        for j in range(W):
            if G[i][j] == "#":
                continue
            if done[j]:
                continue
            length = 0
            while j + length < W:
                if G[i][j+length] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i][j + k] += length
                done[j + k] = 1

    for j in range(W):
        done = [0] * H
        for i in range(H):
            if G[i][j] == "#":
                continue
            if done[i]:
                continue
            length = 0
            while i + length < H:
                if G[i+length][j] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i + k][j] += length
                done[i + k] = 1
    ans = 0
    for i in range(H):
        ans = max(ans, max(cnt[i]) - 1)
    print(ans)


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

h,n=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
  a_num,b_num=map(int,input().split())
  a.append(a_num)
  b.append(b_num)

#dpテーブル　dp[i+1][j]=i番目までの魔法を用いて体力をj以上減らす時の消耗の最小値
dp=[[float("INF") for i in range(h+1)] for j in range(n+1)]
#初期条件
dp[0][0]=0
for i in range(n):
  for j in range(h+1):
    #i番目の魔法を使わない時
    if a[i]>j:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+b[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][h])
  

### FIXED CODE ###

h,n=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
  a_num,b_num=map(int,input().split())
  a.append(a_num)
  b.append(b_num)

#dpテーブル　dp[i+1][j]=i番目までの魔法を用いて体力をj以上減らす時の消耗の最小値
dp=[[float("INF") for i in range(h+1)] for j in range(n+1)]
#初期条件
dp[0][0]=0
for i in range(n):
  for j in range(h+1):
    #i番目の魔法を使わない時
    if a[i]>j:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+b[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][h])