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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:i+5] :
            i += 5
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

A, B, N = map(int, input().split())

def floor(t):
    return int(t)

list = []
for x in range(N+1):
    list.append(floor((A*x)/B) - A*floor(x/B))

print(max(list))

### FIXED CODE ###

A, B, N = map(int, input().split())

def floor(t):
    return int(t)

list = []

if N+1 > B:
    print(floor((A*(B-1))/B) - A*floor((B-1)/B))
else:
    print(floor((A*N/B) - A*floor(N/B)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(1,N):
    a = sum(A[:i])
    b = sum(A[i:])
    B.append(abs(a-b))
print(min(B))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
sum_A = sum(A)
ans = 10**20
X = 0
for a in A[:-1]:
    X += a
    ans = min(ans,abs(sum_A-2*X))
print(ans)
### BUGGY CODE ###

import numpy as np
n, C = map(int,input().split())
cha = [[] for _ in range(C+1)]
stc = [list(map(int, input().split())) for _ in range(n)]
stc.sort()
for s, t, c in stc:
    cha[c].append([s, t])
result = np.zeros(2*10**5)
for i in range(1, C+1):
    x = np.zeros(2*10**5)
    for s, t in cha[i]:
        x[s*2-(x[s*2-1]==0)+2*(x[s*2]==1):t*2] += 1
    result += x
print(int(max(result)))

### FIXED CODE ###

import numpy as np
n, C = map(int,input().split())
cha = [[[0,0]] for _ in range(C+1)]
stc = [list(map(int, input().split())) for _ in range(n)]
stc.sort()
for s, t, c in stc:
    if cha[c][-1][1]==s:
        cha[c][-1][1] = t
    else:
        cha[c].append([s, t])
result = np.zeros(2*10**5)
for i in range(1, C+1):
    for s, t in cha[i]:
        result[s*2-1:t*2] += 1
print(int(max(result)))
### BUGGY CODE ###

from functools import reduce
from collections import Counter

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

LR = reduce(lambda a,b:a+[a[-1]+b],A,[0])
LR = list(map(lambda x:x%M,LR))

Lc = Counter(LR[:-1])
Rc = Counter(LR[1:])
LRCount = Counter(LR)
LRNum = [int(LRCount[k]*(LRCount[k]-1)/2) for k in LRCount]

LRNum = sum(LRNum)
print(LRNum)

### FIXED CODE ###

from functools import reduce
from collections import Counter


def calc(N,M,A):
    LR = [0]
    pa = 0
    for a in A:
        pa += a
        LR.append(pa)
    LR = list(map(lambda x:x%M,LR))

    LRCount = Counter(LR)
    LRNum = [int(LRCount[k]*(LRCount[k]-1)/2) for k in LRCount]
    LRNum = sum(LRNum)
    print(LRNum)

N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
calc(N,M,A)
### BUGGY CODE ###

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

li = []

for i, a in enumerate(A):
    li.append([i+1, a])

ans = 0

for l in li:
    if l[::-1] in li:
        ans += 1

print(ans//2)

### FIXED CODE ###

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

ans = 0

for i in range(N):
    if (i+1)==A[A[i]-1]:
        ans += 1

print(ans//2)
### BUGGY CODE ###

cash = int(input())

n=0
paid =0
while paid < cash:
  paid = 1000 * n 

print(paid - cash)



### FIXED CODE ###

cash = int(input())
 
n = 0
paid = 0
while paid < cash:
  paid = 1000 * n 
  n += 1
 
print(paid - cash)
### BUGGY CODE ###

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

count = n
for i in range(n):
  for j in range(i):
    if p[i] > p[j]:
      count -= 1
      break

print(count)
    

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
m = p[0]
count = 1
for i in range(1,n):
#  print(i, min(p[:i+1]), p[i])
  m = min(m, p[i])
  if m == p[i]:
    count += 1
print(count)
### BUGGY CODE ###

import sys  
input = sys.stdin.readline

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


k = [0]*N
for i in range(M):
    l, r = list(map(int, input().split()))
    for q in range(l-1, r):
        k[q] += 1

ans = 0
for k_ in k:
    if k_ == M:
        ans +=1

print(ans)

### FIXED CODE ###

import sys  
input = sys.stdin.readline

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



ans = -1
l_min , r_max = list(map(int, input().split()))
for i in range(M-1):
    l, r = list(map(int, input().split()))
    if r_max < l or r < l_min:
        ans = 0
        break

    if l_min <= l and l <= r_max:
        l_min = l

    if l_min <= r and r <= r_max:
        r_max = r


if ans == 0:
    print(ans)
else:
    print(r_max - l_min + 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
setA=set(A)
number1={}#-1
number2={}
ans={}
for i in setA:
    tmp=A.count(i) - 1
    souwa=(tmp - 1)*(tmp)//2
    number1[i]=souwa
    souwa=tmp*(tmp+1)//2
    number2[i]=souwa
t=sum(number2.values())
for a in setA:
    total=number1[a]
    total+=t
    total-=number2[a]
    ans[a]=total

for a in A:
    print(ans[a])






### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
d=Counter(A)
dic={}
total=0
for item in d.items():
    counter=item[1]
    s1=(counter - 1)*(counter - 2)/2 #1個少ない
    s2=(counter)*(counter - 1)/2
    dic[item[0]]=int(s1 - s2)
    total+=int(s2)

for a in A:
    print(total + dic[a])
### BUGGY CODE ###

S = input()
Q = int(input())
S = list(S)

A = []
B = []
count = 0

Que = []
ope = []

for i in range(Q):
    k = input()
    if k == "1":
        count += 1
        Que.append("1")
        ope.append("0")
    else:
        Que.append("2")
        ope.append([k[2],k[4]])

cou = 0

if count % 2 == 0:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = [ope[i][1]] + A
            else:
                B = B + [ope[i][1]]
else:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = A + [ope[i][1]]
            else:
                B = [ope[i][1]] + B

if count % 2 == 0:
    S = A + S + B
else:
    S.reverse()
    S = B + S + A

print(*S, sep="")

### FIXED CODE ###

S = input()
Q = int(input())
 
A = ""
B = ""
count = 0

Que = []
ope = []

def rev(s):
    re = ""
    for i in range(len(s)):
        re = re + s[len(s) - 1 - i]
    return re
 
for i in range(Q):
    k = input()
    if k == "1":
        count += 1
        Que.append("1")
        ope.append("0")
    else:
        Que.append("2")
        ope.append([k[2],k[4]])
 
cou = 0
 
if count % 2 == 0:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = ope[i][1] + A
            else:
                B = B + ope[i][1]
else:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = A + ope[i][1]
            else:
                B = ope[i][1] + B
 
if count % 2 == 0:
    S = A + S + B
else:
    S = rev(S)
    S = B + S + A
 
print(S)
### BUGGY CODE ###

s = input()
target = input()
for index in range(len(s)):
    ss = s[index]
    tt = target[index]
	
    if s[:index] != target[:index]:
        break
    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")
### BUGGY CODE ###

def combination(n, k, MOD):
  if(k > n or k < 0):
    return 0
  frac = [1]*(n+1)
  for i in range(1, n+1):
    frac[i] = (frac[i-1]*i)%MOD
  return (frac[n]*pow(frac[k], MOD-2, MOD)*pow(frac[n-k], MOD-2, MOD))%MOD

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
MOD = 10**9+7

ans = 0
for i in range(N):
  ans = (ans + A[i]*combination(i, K-1, MOD))%MOD
for i in range(N):
  ans = (ans - A[i]*combination(N-i-1, K-1, MOD))%MOD
  
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
MOD = 10**9+7

#c[i] := (i)C(K-1)
c = [0] * (N+1)
#frac[i] = i!%MOD
frac = [1] * (N+1)
for i in range(1, N+1):
  frac[i] = (frac[i-1]*i)%MOD
for i in range(1, N+1):
  if(i >= K-1):
    c[i] = frac[i]*pow(frac[K-1], MOD-2, MOD)*pow(frac[i-K+1], MOD-2, MOD)%MOD

  
ans = 0
for i in range(N):
  ans = (ans + A[i]*c[i])%MOD
for i in range(N):
  ans = (ans - A[i]*c[N-i-1])%MOD
  
print(ans)
### BUGGY CODE ###

S = input()

count = 0
while 'BW' in S:
    S = S.replace('BW', 'WB', 1)
    count += 1

print(count)

### FIXED CODE ###

S = input()

count = 0
pre_index = 0
pre_count = 0
for index, value in enumerate(S):
    if value == 'W':
        n = S[pre_index:index].count('B')
        count += n + pre_count
        pre_count = n + pre_count
        pre_index = index

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

N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
while True:
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if j < i:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      gs.append((i, j))
  if gs == []:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  for i, j in gs:
    A[i].pop()
    A[j].pop()
  d += 1
print(d)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
l = list(range(N))
while True:
  n2 = 0
  l2 = []
  s2 = set()
  for i in l:
    if A[i] == []:
      continue
    j = A[i][-1]
    if A[j] == []:
      continue
    if i in s2 or j in s2:
      continue
    if A[j][-1] == i:
      n += 1
      n2 += 1
      s2.add(i)
      s2.add(j)
      l2.append(i)
      l2.append(j)
      A[i].pop()
      A[j].pop()
  if n2 == 0:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  l = l2
  d += 1
print(d)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem D

if __name__ == '__main__':
    number, k = list(map(int, input().split()))

    count = 0

    for i in range(1, number + 1):
        for j in range(1, number + 1):
            if i % j >= k:
                count += 1

    print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem D

if __name__ == '__main__':
    number, k = list(map(int, input().split()))
    count = 0

    # HACK: Not beautiful.
    if k == 0:
        print(number ** 2)
    else:
        for b in range(1, number + 1):
            p = (number + 1) // b
            r = number - (p * b)
            count += p * max(0, b - k)

            if (number + 1) % b != 0:
                count += max(0, r - k + 1)

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

import re

S = input()

steps = 0

while not (re.findall('W*', S)[0] == S or re.findall('B*', S)[0] == S):
    # add one black left
    temp_S = S
    i = 0
    while temp_S[i] != 'B':
        temp_S = temp_S[:i] + 'B' + temp_S[i+1:]

        i += 1
        if i == len(temp_S) - 1:
            if temp_S[i] == 'W':
                temp_S = S
                break
        elif i == len(temp_S):
            break
    if temp_S != S:
        steps += 1
        S = 'B' + temp_S

    # print(S)

    # add one white left
    temp_S = S
    i = 0
    while temp_S[i] != 'W':
        if i == 0:
            temp_S = 'W' + temp_S[1:]
        else:
            temp_S = temp_S[:i] + 'W' + temp_S[i+1:]

        i += 1
        if i == len(temp_S) - 1:
            if temp_S[i] == 'B':
                temp_S = S
                break
        elif i == len(temp_S):
            break
    if temp_S != S:
        steps += 1
        S = 'W' + temp_S

    # print(S)

    # add one black right
    temp_S = S
    i = len(S) - 1
    while temp_S[i] != 'B':
        if i == 0:
            temp_S = 'B' + temp_S[1:]
        else:
            temp_S = temp_S[:i] + 'B' + temp_S[i+1:]

        i -= 1
        if i == 0:
            if temp_S[i] == 'W':
                temp_S = S
                break
        elif i == -1:
            break
    if temp_S != S:
        steps += 1
        S = temp_S + 'B'

    # print(S)

    # add one white right
    temp_S = S
    i = len(S) - 1
    while temp_S[i] != 'W':
        temp_S = temp_S[:i] + 'W' + temp_S[i+1:]

        i -= 1
        if i == 0:
            if temp_S[i] == 'B':
                temp_S = S
                break
        elif i == -1:
            break
    if temp_S != S:
        steps += 1
        S = temp_S + 'W'

    # print(S)
    

# print(S)
print(str(steps))


### FIXED CODE ###

strs = raw_input().strip()
n = len(strs)
bbb = 0
for i in xrange(n-1):
    if strs[i] != strs[i+1]:
        bbb+=1
print(bbb)
### BUGGY CODE ###

n = int(input())
s = []

for item in range(n):
    item = input()
    if(item not in s):
        s.append(item)

print(len(s))

### FIXED CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]

ans = collections.Counter(s)
print(len(ans))
### BUGGY CODE ###

#import time
#time1=time.time()
N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*(N-1)
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in distance:
    print(i)
#time2=time.time()
#print(time2-time1)

### FIXED CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])
### BUGGY CODE ###

from heapq import heappush, heappop

INT_MAX = 10 ** 9


def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  g = [[0] * (n+1) for i in range(n+1)]
  gp = [INT_MAX] * (n+1)
  gf = [0] * (n+1)
  
  for a, b in ab:
    g[a][b] = 1
    g[b][a] = 1
  
  h = [(1, 1, 0)]
  
  while h:
    a, b, p = heappop(h)
    if p < gp[a]:
      gp[a] = p
      gf[a] = b
    else:
      continue
    for z in range(1, n+1):
      if g[a][z]:
        heappush(h, (z, a, p + g[a][b]))
  
  r = gf[2:]
  s = 'Yes' if all(0 < i < INT_MAX for i in r) else 'No'
  print(s)
  if s == 'Yes':
    for i in r:
      print(i)
  
  
  
if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[] for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a].append(b)
    ggg[b].append(a)
    
  qq = deque()
  qq.append(1)
  ff[1] = 1
  
  while qq:
    a = qq.popleft()
    for b in ggg[a]:
      if not ff[b]:
        ff[b] = a
        qq.append(b)
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

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

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1
                explored.add(next)
                for i in route[next]:
                    if i not in explored and i not in stock:
                        stock.append(i)
            ans = max(ans,cnt)
    print(ans)
main()            


### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            explored.add(nnext)
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1   
                for i in route[next]:
                    if i not in explored:
                        stock.append(i)
                        explored.add(i)
            ans = max(ans,cnt)
    print(ans)
main()
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for _ in range(q)]

ans = [k] * n

for i in range(q):
  for j in range(n):
    if a[i]-1 != j :
      ans[j] -= 1
  
for anss in ans:
  print("Yes" if anss > 0 else "No")

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for _ in range(q)]

ans = [0] * n

for i in range(q):
  ans[a[i]-1] += 1
for anss in ans:
  print("Yes" if k - q + anss > 0 else "No")
### BUGGY CODE ###

from statistics import median as m
n=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i-1 for i in range(n)])
print(int(sum([abs(b-m(B)) for b in B])))

### FIXED CODE ###

from statistics import median as m
n=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i-1 for i in range(n)])
mb=m(B)
print(int(sum([abs(b-mb) for b in B])))
### BUGGY CODE ###

n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    d[gol] = sta

for i in range(q):
    sta,val = map(int,input().split())
    ans[sta]+=val
    

for i in range(n):
    gol = i+1
    if gol in d:
        ans[gol]+=ans[d[gol]]
    

anss = ""
for i in range(n):
    anss = anss+str(ans[i+1])+" "
print(anss)

### FIXED CODE ###

n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    d[gol] = sta

for i in range(q):
    sta,val = map(int,input().split())
    ans[sta]+=val
    

for i in range(n):
    gol = i+1
    if gol in d:
        ans[gol]+=ans[d[gol]]
    

for i in range(n):
    print(ans[i+1], " ",end="")
### BUGGY CODE ###

# -*- coding:utf8 -*-

n = int(input())
l = [int(input()) for _ in range(n)]
m = max(l)
for i in range(n):
    if l[i] != m:
        print(m)
    else:
        print(max(l[:i] + l[i+1:]))

### FIXED CODE ###

# -*- coding:utf8 -*-

n = int(input())
l = [int(input()) for _ in range(n)]
m = max(l)
n = sorted(l)[-2]
for i in l:
    if i != m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

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

for i in range(M):
  L,R=map(int, input().split())
  if i==0:
    LR=set(list(range(L,R+1)))
  else:
    LR=LR&set(list(range(L,R+1)))
print(len(LR))

### FIXED CODE ###

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

a=1
b=N
for i in range(M):
  L,R=map(int, input().split())
  a=max(a,L)
  b=min(b,R)
  
if b>=a:
  print(b-a+1)
else:
  print(0)
### BUGGY CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
dp = [float("inf")]*(n)
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(L[i]-L[j]))
        
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
dp = [float("inf")]*(n)
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(L[i]-L[j]))
        
print(dp[n-1])
### BUGGY CODE ###

N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

A = [(tuple(map(int, input().split())), j) for j in range(N)]
B = sorted(A)
C = sorted(A, key=lambda t: ((t[0][1],t[0][0]),t[1]))

#辺の作成
R = []
for i in range(1,N):
  c = B[i][0][0] - B[i-1][0][0]
  p1 = B[i][1]
  p2 = B[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
  
  c = C[i][0][1] - C[i-1][0][1]
  p1 = C[i][1]
  p2 = C[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)

### FIXED CODE ###

N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

B = []
C = []
for i in range(N):
  u, v = map(int, input().split())
  B.append((u, v, i))
  C.append((v, u, i))
B.sort()
C.sort()

#辺の作成
R = []
for i in range(1,N):
  c = B[i][0] - B[i-1][0]
  p1 = B[i][2]
  p2 = B[i-1][2]
  R.append((c, p1, p2))
  
  c = C[i][0] - C[i-1][0]
  p1 = C[i][2]
  p2 = C[i-1][2]
  R.append((c, p1, p2))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)