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

from itertools import permutations

N, M, R = map(int, input().split())
R = list(map(lambda a: int(a) - 1, input().split()))

minDist = [[10**18] * N for _ in range(N)]
for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    minDist[fr][to] = cost
    minDist[to][fr] = cost
for i in range(N):
    minDist[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 10**18
for P in permutations(R, r=len(R)):
    cost = 0
    for fr, to in zip(P, P[1:]):
        cost += minDist[fr][to]
    ans = min(ans, cost)
print(ans)


### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
R = list(map(lambda a: int(a) - 1, input().split()))

minDist = [[10**18] * N for _ in range(N)]
for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    minDist[fr][to] = cost
    minDist[to][fr] = cost
for i in range(N):
    minDist[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 10**18
for P in permutations(R, r=len(R)):
    cost = 0
    for fr, to in zip(P, P[1:]):
        cost += minDist[fr][to]
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

n = input()
l = list(map(int,input().split()))
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for s in l:
        s0 = format(s,"b").zfill(60)
        s0 = s0[::-1]
        if s0[i] == "1": c1 += 1
        else: c0 += 1
    ans += (c1*c0)*(2**i)
print(ans%((10**9)+7))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    c1 = sum([1 for a in l if (a>>i) & 1])
    c0 = n - c1
    ans += (c1*c0)*(2**i)
print(ans%((10**9)+7))
### BUGGY CODE ###

import bisect

n, q = map(int, input().split())
s = input()

questions = []
for i in range(q):
    questions.append(list(map(int, input().split())))

ac_positions = []
for i in range(n):
    if s[i:i + 2] == 'AC':
        ac_positions.append(i + 1)

for question in questions:
    ac_count = 0

    explore_ac_positions = ac_positions[
                           bisect.bisect_left(ac_positions, question[0]):
                           bisect.bisect_right(ac_positions, question[1])]
    for ac_position in explore_ac_positions:
        if question[0] <= ac_position and ac_position + 1 <= question[1]:
            ac_count += 1

    print(ac_count)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
questions = [list(map(int, input().split())) for _ in range(q)]

ac_sum = [0]
for i in range(1, n + 1):
    ac_sum.append(ac_sum[i-1] + 1 if s[i-1 : i+1] == 'AC' else ac_sum[i-1])

for l, r in questions:
    print(ac_sum[r-1] - ac_sum[l-1])
### BUGGY CODE ###

n, W = map(int, input().split())
w, v = [], []
dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

def solve(i, total):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0
    if total > W:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(i+1, total + weight)
        unchose = solve(i+1, total)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(i+1, total)
        return dp[i][total]

print(solve(0, 0))

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

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

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = []
tmp = [0] * (max(C) + 1)
ctr.append(tmp[:])
for i in range(N):
    tmp[C[i]] += 1
    ctr.append(tmp[:])

for l, r in X:
    print(sum(u - v > 0 for u, v in zip(ctr[r], ctr[l - 1])))


### FIXED CODE ###

class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

print(*ans, sep="\n")
### BUGGY CODE ###

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

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(mid, A):
  count = 0
  for i in range(N):
    if A[i] > mid:
      xx = A[i] / mid
      if xx % 1 != 0:
        xx += 1
      count += int(xx - 1)
      
  #print("c", count)
  if count > K:
    return False
  else:
    return True
  
#にぶたん
#A : 配列
def binary_search(A):
  N = 10 ** 9
  ng = -1
  ok = N
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if mid == 0:
      mid = 1
    #print(ng, ok, mid)
    if isOK(mid, A):
      ok = mid
    else:
      ng = mid
  return ok
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]

print(binary_search(A))
  



### FIXED CODE ###

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

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(mid, A):
  count = 0
  for i in range(N):
    if A[i] > mid:
      xx = A[i] / mid
      if xx % 1 != 0:
        xx += 1
      count += int(xx - 1)
      
  #print("c", count)
  if count > K:
    return False
  else:
    return True
  
#にぶたん
#A : 配列
def binary_search(A):
  N = 10 ** 9
  ng = -1
  ok = N
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if mid == 0:
      return 1
    #print(ng, ok, mid)
    if isOK(mid, A):
      ok = mid
    else:
      ng = mid
  return ok
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]

print(binary_search(A))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = {}
    find = False
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        if y == dy and x == dx:
            find = True
            break

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and not used[h][w]:
                    v[(h, w)] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    if find:
        break
    worp += 1
    for h, w in v.keys():
        if not used[h][w]:
            q.append([h, w])
            used[h][w] = True

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

from itertools import product
c = [tuple(map(int, input().split())) for _ in range(3)]

maxNum = max(max(c))
for i in product(range(maxNum+1),repeat=3):
  if max(i) > maxNum: continue
  for x in range(maxNum+1):
    row1 = (i[0]+x,i[1]+x,i[2]+x)
    if row1 == c[0]:
      for y in range(maxNum+1):
        row2 = (i[0]+y,i[1]+y,i[2]+y)
        if row2 == c[1]:
          for z in range(maxNum+1):
            row3 = (i[0]+z,i[1]+z,i[2]+z)
            if row3 == c[2]:
              print("Yes")
              exit()
print("No")

### FIXED CODE ###

c = [list(map(int, input().split())) for _ in range(3)]

# 斜め同士を足し合わせ比較をする
if c[0][0] + c[1][1] == c[0][1] + c[1][0]:
  if c[0][1] + c[1][2] == c[0][2] + c[1][1]:
    if c[1][0] + c[2][1] == c[1][1] + c[2][0]:
      if c[1][1] + c[2][2] == c[1][2] + c[2][1]:
        print("Yes")
        exit()
print("No")
### BUGGY CODE ###

def try_int(s):
    try:
        return int(s)
    except:
        return s

s = input()
nq = int(input())
flg = 0
for i in range(nq):
    q = input()
    if len(q) == 1:
        flg += 1
    else:
        if flg % 2 == 0:
            if q[2] == '1':
                s = q[-1]+s
            else:
                s = s+q[-1]
        else:
            if q[2] == '1':
                s = s+q[-1]
            else:
                s = q[-1]+s
if flg % 2 == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

from sys import stdin
 
def main():
    S = list(stdin.readline().rstrip())
    Q = int(input())
    rev = 0
    head = []
    tail = []
 
    for _ in range(Q):
        q = stdin.readline()
        if q[0] == "1":
            rev = (rev+1)%2
        else:
            if q[2] == "1":
                if rev == 0:
                    head.append(q[4])
                else:
                    tail.append(q[4])
            else:
                if rev ==0:
                    tail.append(q[4])
                else:
                    head.append(q[4])
 
    if rev == 0:
        ans = "".join(head[::-1] + S + tail)
    else:
        ans = "".join(tail[::-1] + S[::-1] + head)
    
    print(ans)
    
main()
### BUGGY CODE ###

import math

def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

def check(ans, ansC, *args):
    n = len(args)
    temp = []
    for i in range(n):
        temp.append(C(args[i][0], args[i][1]))
    ind = temp.index(max(temp))
    temp += [ansC]
    if ind == n:
        return ans, ansC
    else:
        return args[ind - 1], temp[ind]

n = int(input())
a = sorted(list(map(int, input().split())))
ans, ansC = [1, 0], 1

while len(a) > 1:
    A = a.pop(-1)
    if A//2 in a:
        ans, ansC = check(ans, ansC, [A, A//2])
        break
    elif A % 2 != 0 and A//2 + 1 in a:
        ans, ansC = check(ans, ansC, [A, A//2 + 1])
        break
    elif ansC > C(A, A//2):
        break
    else:
        x, i = A//2, 0
        if a[-1] < x:
            ans, ansC = check(ans, ansC, [A, a[-1]])
        else:
            while a[i] < x:
                i += 1
            ans, ansC = check(ans, ansC, [A, a[i]], [A, a[i-1]])

print(ans[0], ans[1])

### FIXED CODE ###

import math
from bisect import bisect_left

def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

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

A = a.pop(-1)
if A//2 in a:
    print(A, A//2)
elif A % 2 != 0 and A//2 + 1 in a:
    print(A, A//2 + 1)
else:
    x = A//2
    temp = bisect_left(a, x)
    if temp == 0:
        print(A, a[0])
    elif temp == len(a):
        print(A, a[-1])
    else:
        print(A, a[sorted([temp, temp - 1], key = lambda y: abs(x - a[y]))[0]])
### BUGGY CODE ###

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

dp = [0]  * (W + 1)
items = []
for i in range(N):
  w, v = map(int, input().split())
  items.append((w, v))

for w, v in items:  
  for wk in range(W, w - 1, -1):
    tv = dp[wk - w] + v
    if tv > dp[wk]:
      dp[wk] = tv
res = max(dp)
print(res)


### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()

    code_pattern = set()

    for i in range(0, N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                code_pattern.add(S[i]+S[j]+S[k])

    print(len(code_pattern))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()

    count = 0

    for i in range(10):
        a = S.find(str(i))
        if a == -1:
            continue

        for j in range(10):
            b = S[a+1:].find(str(j))
            if b == -1:
                continue

            for k in range(10):
                if str(k) in S[a+b+2:]:
                    # print(i*100+j*10+k)
                    count += 1

    print(count)


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

def main():
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    f=sorted(list(map(int,input().split())),reverse=True)
    def b_search(a,b,value,lim):
        med=(a+b)//2
        if a==b:return a
        elif lim=="upper":
            if a+1==b:
                if value(b):return b
                else:return a
            elif value(med):return b_search(med,b,value,lim)
            else:return b_search(a,med-1,value,lim)
        else:
            if a+1==b:
                if value(a):return a
                else:return b
            elif value(med):return b_search(a,med,value,lim)
            else:return b_search(med+1,b,value,lim)

    def count(val):
        cnt=0
        for i in range(n):
            cnt+=max(a[i]-val//f[i],0)
        if cnt>k:
            return False
        else:
            return True
    
    print(b_search(0,10**12+10,count,"lower"))
    
main()

### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    f=sorted(list(map(int,input().split())),reverse=True)
    def b_search(a,b,value,lim):
        med=(a+b)//2
        if a==b:return a
        elif lim=="upper":
            if a+1==b:
                if value(b):return b
                else:return a
            elif value(med):return b_search(med,b,value,lim)
            else:return b_search(a,med-1,value,lim)
        else:
            if a+1==b:
                if value(a):return a
                else:return b
            elif value(med):return b_search(a,med,value,lim)
            else:return b_search(med+1,b,value,lim)

    def count(val):
        cnt=0
        for i in range(n):
            cnt+=max(a[i]-val//f[i],0)
        if cnt>k:
            return False
        else:
            return True
    
    print(b_search(0,10**12+10,count,"lower"))
    
main()
### BUGGY CODE ###

from fractions import gcd
a,b,c,d = map(int,input().split())
if c <=0 or d <= 0:
    print("No")
ans = c * d // gcd(c,d)
i = a
j = a
while True:
    if i % c == 0:
        break
    i += 1
while True:
    if j % d == 0:
        break
    j += 1
k = min(i,j)
while True:
    if k % ans == 0:
        break
    k += 1
ii = (b-i)//c 
jj = (b-j)//d 
kk = (b-k)//ans 
print(b-a-ii-jj+kk)


### FIXED CODE ###

a,b,c,d = map(int,input().split())
cc = b//c -(a-1)//c
dd = b//d -(a-1)//d
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)
cd = lcm(c, d)
cdcd = b//cd -(a-1)//cd
print(b-a+1-cc-dd+cdcd)
### BUGGY CODE ###

data = input()
l = data.split()
l = list(map(int, l))

points = [l[1] for i in range(l[0])]

for i in range(l[2]):
    a = int(input()) - 1
    for j in range(l[0]):
        if j != a:
            points[j] -= 1

for p in points:
    if p <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

data = input()
l = data.split()
l = list(map(int, l))
p = l[1] - l[2]

points = [p for i in range(l[0])]

for i in range(l[2]):
    a = int(input()) - 1
    points[a] += 1

for p in points:
    if p <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = tuple(list(map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for lrd in lrds:
        lrd[0] -= 1
        lrd[1] -= 1
        l, r, d = lrd
        g[l].append((r, d))
        g[r].append((l, -d))

    while None in x:
        inone = x.index(None)
        stack = [inone]
        x[inone] = 0
        while len(stack) > 0:
            i = stack.pop()
            for j, d in g[i]:
                if not x[j]:
                    stack.append(j)
                    x[j] = x[i] + d

    for l, r, d in lrds:
        if x[r] - x[l] != d:
            print('No')
            sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

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

L,R = map(int,input().split())
 
ans = 2019
m = []
for i in range(L,R+1):
	m.append(i%2019)
 
for i in range(len(m)):
	for j in range(i+1,len(m)):
		tmp = (m[i]*m[j])%2019
		if ans> tmp:
			ans = tmp
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
 
ans = 2019
m = []
l = R-L+1
if l < 2019:
	for i in range(L,R+1):
		m.append(i%2019)
else:
	for i in range(L,L+2019):
		m.append(i%2019)

for i in range(len(m)):
	for j in range(i+1,len(m)):
		tmp = (m[i]*m[j])%2019
		if ans> tmp:
			ans = tmp
		if tmp == 0:
			break				
print(ans)
### BUGGY CODE ###

from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

xl = list(map(lambda p: p[0],
              points))
yl = list(map(lambda p: p[1],
              points))

def contained(point, xmin, xmax, ymin, ymax):
    return (xmin <= point[0] <= xmax) and (ymin <= point[1] <= ymax)

def count_contained(xmin, xmax, ymin, ymax):
    count = 0
    for point in points:
        if contained(point, xmin, xmax, ymin, ymax):
            count += 1
    return count

min_area = 10**20
for xs in combinations(xl, 2):
    xmin = min(xs)
    xmax = max(xs)
    for ys in combinations(yl, 2):
        ymin = min(ys)
        ymax = max(ys)
        if count_contained(xmin, xmax, ymin, ymax) >= K:
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)
print(min_area)


### FIXED CODE ###

from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

xl = list(map(lambda p: p[0],
              points))
yl = list(map(lambda p: p[1],
              points))

def contained(point, xmin, xmax, ymin, ymax):
    return (xmin <= point[0] <= xmax) and (ymin <= point[1] <= ymax)

def count_contained(xmin, xmax, ymin, ymax):
    count = 0
    for point in points:
        if contained(point, xmin, xmax, ymin, ymax):
            count += 1
    return count

min_area = 10**20
for xs in combinations(xl, 2):
    xmin = min(xs)
    xmax = max(xs)
    for ys in combinations(yl, 2):
        ymin = min(ys)
        ymax = max(ys)
        if count_contained(xmin, xmax, ymin, ymax) >= K:
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)
print(min_area)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    dp = [float("inf")] * 10 ** 6
    h = h + [0] * 10 ** 6
    dp[0] = 0
    for i in range(N):
        for j in range(1, K + 1):
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
    print(dp[N - 1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

dp = [float("inf")] * 10 ** 6
h = h + [0] * 10 ** 6
dp[0] = 0
for i in range(N):
    for j in range(1, K + 1):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[N - 1])
### BUGGY CODE ###

import sys

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

a.insert(0, -1)

env = [0] * (n+1)
hako = [0] * (n+1)
ind = []

for _ in range(n):
    i = n - _
    if a[i] != env[i]:
        hako[i] = 1
        ind.append(str(i))
        yakusuu = make_divisors(i)
        for j in yakusuu:
            if env[j] == 0:
                env[j] = 1
            else:
                env[j] = 0

goukei = sum(hako)
print(goukei)
if ind == []:
    sys.exit()
mojiretu = ' '.join(ind)
print(mojiretu)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

a.insert(0, -1)

env = [0] * (n+1)
hako = [0] * (n+1)
ind = []

for _ in range(n):
    i = n - _
    if a[i] != env[i]:
        hako[i] = 1
        ind.append(str(i))
        yakusuu = make_divisors(i)
        for j in yakusuu:
            if env[j] == 0:
                env[j] = 1
            else:
                env[j] = 0

goukei = sum(hako)
print(goukei)
if ind != []:
    mojiretu = ' '.join(ind)
    print(mojiretu)