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

N, x = map(int, input().split())
a = list(map(int, input().split()))
min_a = a[:]
ans = 10 ** 18
for i in range(N):
    s = x * i
    for j in range(N):
        min_a[j] = min(min_a[j], a[(i + j) % N])
        s += min_a[j]
    ans = min(ans, s)
print(ans)

### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
min_a = []
for i in a:
    min_a.append(i)
ans = 10 ** 18
for i in range(N):
    s = x * i
    for j in range(N):
        min_a[j] = min(min_a[j], a[(i + j) % N])
        s += min_a[j]
    ans = min(ans, s)
print(ans)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def popcnt1(n):
	return bin(n).count("1")

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a | b

	# セグメント木の中身をリストAで初期化
	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = 1 << A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return popcnt1(m)


#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	Seg = SegmentTree(N)
	Seg.initialize(c)
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		ans = Seg.query(l, r)
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

	ans = [0] * Q
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



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

n, q = map(int, raw_input().split())
s = [0]*n
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	ss = sorted(s,reverse=True)
	print s.index(ss[0])+1,ss[0]

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = [0]*n
mx,mxa = 0, 0
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	if v > 0:
		if s[a-1] > mx:
			mx = s[a-1]
			mxa = a-1
		elif s[a-1] == mx:
			if a-1 < mxa:
				mxa = a-1
	elif v < 0:
		if a-1 == mxa:
			mx = max(s)
			mxa = s.index(mx)
	print mxa+1,mx
### BUGGY CODE ###

N,M=map(int,input().split())
C={i for i in range(1,N+1)}

for _ in range(M):
    LR=list(map(int,input().split()))
    C=C&{k for k in range(LR[0],LR[1]+1)}
print(len(C))

### FIXED CODE ###

N,M=map(int,input().split())
LR=list(list(map(int,input().split())) for _ in range(M))
L=1
R=N
for i in range(M):
    L=max(L,LR[i][0])
    R=min(R,LR[i][1])
print(R-L+1 if L<=R else 0)
### BUGGY CODE ###

# よくわからんので、O(N**3)をやってみる
n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [[[0]*(n+1) for _ in range(W_MAX+1)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(1, n+1):
    a = A[i-1]
    for j in range(W_MAX+1):
        for k in range(n):
            dp[i][j][k] += dp[i-1][j][k]
            if W_MAX < j+a:
                continue
            dp[i][j+a][k+1] += dp[i-1][j][k]

ans = 0
for k in range(1, n+1):
    cnt = dp[-1][-1][k]
    ans += cnt*pow(2, n-k, MOD)
print(ans % MOD)

### FIXED CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [0]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
ans=0
while xh:
    tmp=xh.pop()
    # print(tmp)
    if tmp[1]<=0:
        continue
    zahyo=tmp[0]-d*2
    kaisu=math.ceil(tmp[1]/a)
    ans+=kaisu
    # print(zahyo,kaisu)
    for i in range(len(xh)):
        if xh[-1-i][0]>=zahyo:
            xh[-1-i][1]-=kaisu*a
        else:
            break
print(ans)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[],[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r.append(x+2*d)

print(tama[-1])
# print(r)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
  i = A.index(max(A))
  A[i] = A[i]//2
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
  A[i] = -A[i]
heapq.heapify(A)
for _ in range(M):
  a = -heapq.heappop(A)
  a = (a//2) * -1
  heapq.heappush(A, a)
print(sum(A)*-1)
### BUGGY CODE ###

L=list()
s=input()
K=int(input())
if len(s)<10:
  for i in range(len(s)):
    for j in range(i+1,len(s)+1):
      L.append(str(s[i:j]))
  L=sorted(list(set(L)))
  print(L[K-1])
else:
  A=sorted(list(s))
  B=[A[0],A[1],A[2],A[3],A[4]]
  for i in range(len(s)):
    if s[i] in B:
      for j in range(i+1,len(s)+1):
        L.append(str(s[i:j]))
      L=sorted(list(set(L)))
      if len(L)>K:
        L=list(L[:K])
  print(L[K-1])

### FIXED CODE ###

L=list()
s=input()
K=int(input())
if len(s)<10:
  for i in range(len(s)):
    for j in range(i+1,len(s)+1):
      L.append(str(s[i:j]))
  L=sorted(list(set(L)))
  print(L[K-1])
else:
  A=sorted(list(s))
  B=[A[0],A[1],A[2],A[3],A[4]]
  for i in range(len(s)):
    if s[i] in B:
      for j in range(i+1,min(i+6,len(s)+1)):
        L.append(str(s[i:j]))
      L=sorted(list(set(L)))
      if len(L)>K:
        L=list(L[:K])
  print(L[K-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = []
T = []
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    S.append(s)
    T.append(t)
    X.append(x)

D = []
for _ in range(Q):
    D.append(int(input()))

# 出発時間が区間[S -X, T - X)にあれば工事に引っかかる
W = [(S[i] - X[i], T[i] - X[i]) for i in range(N)]

for q in range(Q):
    ans = []
    for i, (s, t) in enumerate(W):
        if D[q] >= s and D[q] < t:
            ans.append(X[i])
    if len(ans) == 0:
        print(-1)
    else:
        print(min(ans))

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            

for a in ans:
    print(a)
### BUGGY CODE ###

(k, s) = list(map(int, input().split()))
count = 0
for x in range(k + 1):
    if s - x > k * 2:
        continue
    for y in range(k + 1):
        if s - x - y > k:
            continue
        for z in range(k + 1):
            if s == x + y + z:
                count += 1
print(count)

### FIXED CODE ###

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

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = set(A)
L = []
for i in B:
    tmp = 0
    while i in A:
        A.remove(i)
        tmp += 1
    L.append(tmp)
L.sort()
if len(B) <= K:
    print('0')
else:
    print(str(sum(L[0:len(B)-K])))


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = set(A)
    L = [0 for i in range(N+1)]
    for i in A:
        L[i] += 1
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print(str(sum(L[0:N+1-K])))


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

N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

for i in range(N):
    w, v = map(int, input().split())
    wv[i] = [w, v]

dp = [[0 for i in range(2*W)] for j in range(2*N)]

for i in range(N):
    for j in range(W+1):
        if (j - wv[i][0] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

for i in range(N):
    w, v = map(int, input().split())
    wv[i] = [w, v]

dp = [[0 for i in range(2*W)] for j in range(2*N)]

for i in range(N):
    for j in range(W+1):
        if (j - wv[i][0] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
import bisect
for i in range(M):
    bisect.insort(A,A[-1]//2)
    A.pop(-1)
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
import bisect
for i in range(M):
    bisect.insort(A,A[-1]/2)
    A.pop(-1)
for i in range(N):
    A[i] = int(A[i])
print(sum(A))
### BUGGY CODE ###

n,m=map(int,input().split())
L=[int(input()) for i in range(m)]
 
NL=[0]*(n+1)
NL[0],NL[1]=1,1
 
if 1 in L:
      NL[1]=0
      
for i in range(2,n+1):
      if i in L:
            NL[i]=0
      else:
            NL[i]=NL[i-2]+NL[i-1]
          
if NL[-1]>=1000000007:
  print(NL[-1]%1000000007)
else:
  print(NL[-1])

### FIXED CODE ###

n,m=map(int,input().split())
A=[int(input()) for i in range(m)]

ai=0
n1,n2=0,1
for i in range(1,n+1):
      if ai<m and i==A[ai]:
            ai+=1
            n1=n2
            n2=0
      else:
            tmp=n2
            n2=(n1+n2)%1000000007
            n1=tmp
print(n2)
### BUGGY CODE ###

n=int(input())
x=list(map(lambda x:int(x), input().split()))
mi = int(n/2)-1
for i in range(n):
    cx = x[:]
    del	cx[i]
    cx.sort()
    print(cx[mi])

### FIXED CODE ###

n=int(input())
x=list(map(lambda x:int(x), input().split()))
mi = n//2 - 1
sx=sorted(x)
for item in x:
    if item > sx[mi]:
        print(sx[mi])
    else:
        print(sx[mi+1])
### BUGGY CODE ###

MOD = (10**9) + 7

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

cnt = [0] * 60
for num in a:
    for j in range(60):
        cnt[j] += (num >> j) % 2

ans = 0
for b in range(60):
    ans += cnt[b] * (n - cnt[b]) << b
    ans %= MOD

print(ans)



### FIXED CODE ###

MOD = (10**9) + 7

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

cnt = [0] * 60
for num in a:
    for j in range(60):
        cnt[j] += (num >> j) % 2

ans = 0
for b in range(60):
    ans += cnt[b] * (n - cnt[b]) << b
    ans %= MOD

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

x,k,d = list(map(int,input().split()))
dis = x
cnt = 0
def zet(x):
    if x >= 0:
        return x
    else:
        return -x
while cnt<k:
    if zet(dis)<d:
        recnt = k -cnt
        if recnt%2==0:
            pass
        else:
            dis = d-zet(dis)
        break
    elif dis>=0:
        dis = dis - d
    else:
        dis = dis + d
    cnt += 1
print(zet(dis))

### FIXED CODE ###

x,k,d = list(map(int,input().split()))
x = abs(x)
point =x % d
num = x//d
if num<k:
    rest = k - num
    if rest%2==0:
        pass
    else:
        point = d -point
else:
    point = x - k*d
print(point)
### BUGGY CODE ###

from sys import stdin

def main():
    n = int(input())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    m = 10 ** 9 + 7
    s = 0
    for i in range(len(A)-1):
        b_sum = sum(A[i+1:]) % m
        ans = A[i] * b_sum % m
        s += ans

    s = s % m
    print(s)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():
    n = int(input())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    m = 10 ** 9 + 7
    s = 0
    b_sum = sum(A)
    for i in range(len(A)-1):
        b_sum = b_sum -A[i]
        rest = b_sum % m
        ans = A[i] * rest % m
        s += ans

    s = s % m
    print(s)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

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

MAP = [[min(i, j, N-i-1, N-j-1) for i in range(N)] for j in range(N)]

d = [[1 for i in range(N)] for j in range(N)]

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] > MAP[x][y] + d[x][y]:
            MAP[nx][ny] = MAP[x][y] + d[x][y]
            dfs(nx, ny, cnt + d[x][y])

ans = 0

for p in P:
    x = (p-1) // N
    y = (p-1) % N
    d[x][y] = 0
    cnt = float('INF')
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N:
            cnt = min(cnt, MAP[nx][ny] + d[nx][ny])
        else:
            cnt = min(cnt, 0)
    
    ans += MAP[x][y]
    
    MAP[x][y] = cnt
    
    dfs(x, y, cnt)
    

print(ans)

### FIXED CODE ###

from collections import deque

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

MAP = [min(i, j, N-i-1, N-j-1) for i in range(N) for j in range(N)]

d = [1] * (N ** 2)

ans = 0

def update(np, p):
    if MAP[np] > MAP[p] + d[p]:
        q.append(np)
        MAP[np] = MAP[p] + d[p]

for p in P:
    p -= 1
    
    d[p] = 0
    
    ans += MAP[p]
    
    q = deque()
    
    q.append(p)
    
    while len(q) != 0:
        p = q.popleft()
        if p % N != N-1:
            update(p+1, p)
        if p % N != 0:
            update(p-1, p)
        if p // N != N-1:
            update(p+N, p)
        if p // N != 0:
            update(p-N, p)

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

a = int(input())
s = 1
for i in range(1,a+1):
    s*=i
print(s%1000000007)

### FIXED CODE ###

a = int(input())
s = 1
for i in range(1,a+1):
    s*=i
    s=s%1000000007
print(s)
### BUGGY CODE ###

n = int(input())
x = input()
c = x.count("1")
memo = [0]*(n+1)
p = [0]*n
d = 1
for i in range(n)[::-1]:
    p[i] = d
    d *= 2
s = int(x,2)
for i in range(n):
    if x[i] == "1":
        tmp = s-p[i]
        ctmp = c-1
    else:
        tmp = s+p[i]
        ctmp = c+1
    cnt = 0
    while tmp != 0:
        cnt += 1
        tmp %= ctmp
        tmp2 = tmp
        ctmp = 0
        while tmp2 != 0:
            tmp2,r = tmp2//2,tmp2%2
            ctmp += r
    print(cnt)

### FIXED CODE ###

n = int(input())
x = input()
popcnt = x.count("1")

def powmod(lst,mod):
    if not mod: return
    d = 1
    for i in range(n)[::-1]:
        d %= mod
        lst[i] = d
        d *= 2

def xmod(mod):
    if not mod: return 
    res = 0
    d = 1
    for i in range(n)[::-1]:
        d %= mod
        if int(x[i]):
            res += d
            res %= mod
        d *= 2
    return res

def solve(x):
    res = 1
    while x != 0:
        popcnt = 0
        for i in range(20):
            if x>>i & 1: popcnt += 1
        x %= popcnt
        res += 1
    return res
    
powlst0 = [0]*n
powlst1 = [0]*n
powmod(powlst0,popcnt+1)
x0 = xmod(popcnt+1)
powmod(powlst1,popcnt-1)
x1 = xmod(popcnt-1)

for i in range(n):
    if int(x[i]):
        if popcnt == 1: print(0)
        else: print(solve((x1-powlst1[i])%(popcnt-1)))
    else: print(solve((x0+powlst0[i])%(popcnt+1)))
### BUGGY CODE ###

def count_up(N, A, x, check, card, total):
  if check == N:
    return 1 if card > 0 and card * A == total else 0
  else:
    return count_up(N, A, x, check+1, card+1, total+x[check]) + count_up(N, A, x, check+1, card, total)

def bad_method(N, A, x):
  print count_up(N, A, x, 0, 0, 0)

def well_method(N, A, x):
  dp = [[[1 for a in range(N*50)] for b in range(N+1)] for c in range(N+1)]
  for j in range(N+1):
    for k in range(N+1):
      for s in range(N*50):
        if j == 0 and k == 0 and s == 0:
          dp[j][k][s] = 1
        elif j >= 1 and s < x[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif j >= 1 and k >= 1 and s >= x[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
        else:
          dp[j][k][s] = 0

  answer = 0
  for i in range(1, N+1):
    answer += dp[N][i][A * i]
  print answer

line = raw_input().split()
N = int(line[0])
A = int(line[1])
line = raw_input().split()
x = {}
for i in range(N):
  x[i] = int(line[i])

# bad_method(N, A, x)
well_method(N, A, x)

### FIXED CODE ###

def count_up(N, A, x, check, card, total):
  if check == N:
    return 1 if card > 0 and card * A == total else 0
  else:
    return count_up(N, A, x, check+1, card+1, total+x[check]) + count_up(N, A, x, check+1, card, total)

def bad_method(N, A, x):
  print count_up(N, A, x, 0, 0, 0)

def well_method(N, A, x):
  dp = [[[1 for a in range(N*50)] for b in range(N+1)] for c in range(N+1)]
  for j in range(N+1):
    for k in range(N+1):
      for s in range(N*50):
        if j == 0 and k == 0 and s == 0:
          dp[j][k][s] = 1
        elif j >= 1 and s < x[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif j >= 1 and k >= 1 and s >= x[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
        else:
          dp[j][k][s] = 0

  answer = 0
  for i in range(1, N+1):
    answer += dp[N][i][A * i]
  print answer

def good_method(N, A, x):
  y = {}
  for i in range(len(x)):
    y[i] = x[i] - A
  dp = [[0 for a in range(N*50*2+1)] for b in range(N+1)]
  for j in range(N+1):
    for t in range(N*50*2+1):
      if j == 0 and t == N*50:
        dp[j][t] = 1
      elif j >= 1 and (t - y[j-1] < 0 or t - y[j-1] > N*50*2):
        dp[j][t] = dp[j-1][t]
      elif j >= 1 and 0 <= t - y[j-1] and t - y[j-1] <= N*50*2:
        dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
      else:
        dp[j][t] = 0

  print dp[N][N*50]-1

line = raw_input().split()
N = int(line[0])
A = int(line[1])
line = raw_input().split()
x = {}
for i in range(N):
  x[i] = int(line[i])

# bad_method(N, A, x)
# well_method(N, A, x)
good_method(N, A, x)
### BUGGY CODE ###

N, Q = map(int, input().split())
vws = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(Q)]

anss = []
for v, w in vws:
    parVs, parWs = set(), set()
    while v >= 0:
        parVs.add(v)
        v = (v-1)//N
    while w >= 0:
        parWs.add(w)
        w = (w-1)//N
    anss.append(max(parVs & parWs) + 1)

print('\n'.join(map(str, anss)))


### FIXED CODE ###

N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))
### BUGGY CODE ###

K = int(input())
memo = {}
def gcd(x,y):
    if x < y:
        x,y = y,x
    if (x,y) in memo:return memo[(x,y)]
    if y == 0:return x
    memo[(x,y)] = gcd(y,x%y)
    return memo[(x,y)]
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,gcd(j,k))
print(ans)

### FIXED CODE ###

import math
 
k = int(input()) + 1
ans = 0
 
for a in range(1, k):
    for b in range(1, k):
        d = math.gcd(a, b)
        for c in range(1, k):
            ans += math.gcd(d, c)
 
print(ans)
### BUGGY CODE ###

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

ln.sort()

def binary_search(x, r):
    left = r + 1
    right = n-1
    while left < right:
        mid = (left + right) // 2
        if ln[mid] == x:
            return mid
        elif ln[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    mid = (left + right) // 2
    if ln[mid] > x:
        return mid - 1
    else:
        return mid


ans = 0
for a in range(n-2):
    for b  in range(a+1, n-1):
        cmin = ln[b] - ln[a] + 1
        cmax = ln[b] + ln[a] - 1
        ans += max(0, binary_search(cmax, b) - b)

print(ans)

### FIXED CODE ###

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

ln.sort()

def binary_search(x, r):
    left = r + 1
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if ln[mid] >= x:
            right = mid - 1
        else:
            left = mid + 1
    if ln[mid] >= x:
        return mid - 1
    else:
        return mid


ans = 0
for a in range(n-2):
    for b  in range(a+1, n-1):
        cmax = ln[b] + ln[a]
        ans += max(0, binary_search(cmax, b) - b)

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

# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  lHn  = list(map(int, input().split()))
  lDP  = [0]*iK
  naLen = np.zeros(iK,dtype=int)
  for iI0 in range(1, iNum):
    lRange = range(max([0, iI0 - iK]), iI0)
    iLen = len(lRange)
    for iI2, iI1 in enumerate(lRange):
      naLen[iI2] = lDP[iI1%iK] + abs(lHn[iI0] - lHn[iI1])
    lDP[iI0%iK] = naLen[:iLen].min()
    #print(iI0, lDP, lLen)
  print(lDP[(iNum-1)%iK])

if __name__ == '__main__':
  fnSolv()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  naHn  = np.array(list(map(int, input().split())))
  naDP  = np.zeros(iNum, dtype='int64')
  naLen = np.ones(iK) * 10**9
  for iI0 in range(1, iNum):
    iK0 = min([iK, iI0])
    naLen = naDP[iI0-iK0:iI0] + np.abs(- naHn[iI0-iK0:iI0] + naHn[iI0])
    naDP[iI0] = naLen.min()
  print(naDP[iNum-1])

if __name__ == '__main__':
  fnSolv()