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

data = input().split()
n = int(data[0])
m = int(data[1])
edge=[]
for i in range(m):
    tmp = []
    data = input().split()
    tmp.append(int(data[0]))
    tmp.append(int(data[1]))
    edge.append(tmp)

for i in range(m):
    ans = list(range(1, n+1))
    edge.pop(0)
    for j in edge:
        ans = [ans[j[0]-1] if s == ans[j[1]-1] else s for s in ans]

    res=int(n*(n-1)/2)
    for j in range(1, n+1):
        c = ans.count(j)
        res -= int(c*(c-1)/2)
    print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

data = input().split()
n = int(data[0])
m = int(data[1])
edge=[]
for i in range(m):
    tmp = []
    data = input().split()
    tmp.append(int(data[0])-1)
    tmp.append(int(data[1])-1)
    edge.append(tmp)

grp=list(range(0, n))
def group(num):
    if grp[num] == num:
        return num
    return group(grp[num])

def merge(p_num, c_num):
    grp[c_num]=grp[p_num]

res=[]
ans = [1]*n
ben = int(n*(n-1)/2)
edge.reverse()
for e in edge:
    #print(e, ans, ben, grp)
    res.append(ben)
    g0 = group(e[0])
    g1 = group(e[1])
    if g0 != g1:
        ben -= ans[g0]*ans[g1]
        sum = ans[g0]+ans[g1]
        if ans[g0] > ans[g1]:
            merge(g0, g1)
        else:
            merge(g1, g0)
        ans[g0]=sum
        ans[g1]=sum

res.reverse()
for r in res:
    print(r)

#print(int(n*(n-1)/2))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A_mod = [a % mod for a in A]
    ans = 0
    for i in range(N-1):
        sum_mod = sum(A_mod[i+1:]) % mod
        mul_mod = (A_mod[i] * sum_mod) % mod
        ans = (ans + mul_mod) % mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A_cum_sum = [A[-1]]
    for a in A[::-1][1:]:
        A_cum_sum.append(a + A_cum_sum[-1])
    A_cum_sum = A_cum_sum[::-1]
    ans = 0
    for i in range(N-1):
        sum_mod = A_cum_sum[i+1] % mod
        mul_mod = (A[i] * sum_mod) % mod
        ans = (ans + mul_mod) % mod
    print(ans)


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

h, w = map(int, input().split())
Black = []
White = []

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([i,j])
        else:
            White.append([i,j])

longest = 0
for white in White:
    white_x = white[0]
    white_y = white[1]
    shortest_per_white = 10**4
    for black in Black:
        length = abs(black[0]-white_x) + abs(black[1]-white_y)
        shortest_per_white = min(shortest_per_white, length)
    longest = max(shortest_per_white, longest)

print(longest)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Black = deque([])
Black_grid = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([j,i])
            Black_grid[i][j] = 0

Move = [[-1,0],[1,0],[0,-1],[0,1]]

while Black:
    now = Black.popleft()
    x = now[0]
    y = now[1]
    for move in Move:
        x_next = x + move[0]
        y_next = y + move[1]
        if x_next < 0 or x_next >= w or y_next < 0 or y_next >= h:
            continue
        elif Black_grid[y_next][x_next] >= 0:
            continue
        else:
            Black.append([x_next, y_next])
            Black_grid[y_next][x_next] = Black_grid[y][x] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, Black_grid[i][j])
    
print(ans)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	
D = [int(input()) for _ in range(Q)]

event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
working = [] #現在行われている工事のリスト
n = 0 #現在行われている工事の数

for i in range(Q):
	event.append((D[i], 2))
	
for i in range(N):
	bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
	bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
	
for l in event:
	if l[1] == 1:
		bisect.insort(working, l[2])
		n += 1
	elif l[1] == 0:
		del working[bisect.bisect(working, l[2]) - 1]
		n -= 1
	else:
		if n > 0:
			print(working[0])
		else:
			print(-1)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N
work = []

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	work.append((X[i], S[i] - X[i], T[i] - X[i]))

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

work.sort()
ans = [-1] * Q
skip = [-1] * Q

for i in range(N):
	left = bisect.bisect_left(D, work[i][1])
	right = bisect.bisect_left(D, work[i][2])
	
	while left < right:
		if skip[left] == -1:
			skip[left] = right
			ans[left] = work[i][0]
			left += 1
		else:
			left = skip[left]					
		
for i in ans:
	print(i)
### BUGGY CODE ###

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

A=[]
for i in range(Q):
    A.append(int(input()))

ans_list = [K] * N
# print(ans_list)

for i in range(Q):
    for j in range(N):
        if j != A[i]-1:
            ans_list[j] -=1
#     print(ans_list)
for i in range(N):
#     print(ans_list[i])
    if ans_list[i] > 0:
          print("Yes")
    else:
          print("No")

### FIXED CODE ###

import collections
N,K,Q = map(int,input().split())

A=[]
for i in range(Q):
    A.append(int(input()))
    
jud = Q - K

ans_list = [0] * N

c = collections.Counter(A)
key = list(c.keys())
val = list(c.values())
for i in range(len(c)):
  ans_list[key[i]-1] = val[i]

for i in range(len(c)):
    if val[i] > jud:
        ans_list[key[i]-1] +=1
for i in range(N):
    if ans_list[i] > jud:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  while idx < M :
    if sh[idx] == 0:
      sh[idx] = idx+1
      sh[x["d"]] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
print(ans)

### FIXED CODE ###

def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1: 
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res

n, m = map(int, input().split())
 
li = [[] for j in range(10**5+1)]
 
for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)
 
ans = 0
jobsHeap = []
for i in range(1, m+1):
  for val in li[i]:
    jobsHeap = insertHeap(jobsHeap, val)
  
  if jobsHeap != []:
    res = desertHeap(jobsHeap)
    ans += res
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()


def nextpermutation(s,cnt):
	out = 0
	if cnt == 3:
		j = 0
		for i in range(N):
			if S[i] == s[j]:
				j += 1
			if j == 3:
				return 1
		return 0

	for i in range(10):
		s += str(i)
		out += nextpermutation(s,cnt+1)
		s = s[:-1]

	return out

ans = nextpermutation('', 0)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
t = []
for i in range(10):
	if str(i) not in S:
		t.append(i)
cnt = 0
flg1 = [0] * 10
ind1 = 0
for i in t:
	flg1[i] = 1
while True:
	if flg1[int(S[ind1])] == 1:
		ind1 += 1
	else:
		flg2 = [0] * 10
		for i in t:
			flg2[i] = 1
		ind2 = ind1 + 1
		while True:
			if flg2[int(S[ind2])] == 1:
				ind2 += 1
			else:
				flg3 = [0] * 10
				for i in t:
					flg3[i] = 1
				ind3 = ind2 + 1
				while True:
					if flg3[int(S[ind3])] == 1:
						ind3 += 1
					else:
						flg3[int(S[ind3])] = 1
						cnt += 1
						ind3 += 1

					if flg3.count(0) == 0:
						break
					if ind3 == N:
						break
				flg2[int(S[ind2])] = 1
				ind2 += 1
			if flg2.count(0) == 0:
				break
			if ind2 == N-1:
				break
		flg1[int(S[ind1])] = 1
		ind1 += 1
	if flg1.count(0) == 0:
		break
	if ind1 == N-2:
		break

print(cnt)
### BUGGY CODE ###

import sys
import numpy as np

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a, b = A.shape
    c, d = B.shape
    # print(a, b, c, d)
    assert(b == c)
    ans = np.zeros((a, d), dtype=np.int64)
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    return ans


N, K = na()
A = np.array(naa(N), dtype=np.int32)
mod = 10 ** 9 + 7

B = matrix_pow(A, K, mod)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (ans + B[i][j]) % mod


print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a = len(A)
    b = len(A[0])
    c = len(B)
    d = len(B[0])

    assert(b == c)
    ans = [[0] * d for _ in range(a)]
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    return ans


N, K = na()
A = naa(N)
mod = 10 ** 9 + 7

B = matrix_pow(A, K, mod)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (ans + B[i][j]) % mod


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

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
mod = 2020
for i in range(a, b):
    for j in range(i+1, b+1):
        if i*j%2019 < mod:
            mod = i*j%2019
print(mod)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
if b-a>=673:
    print(0)
else:
    x=[]
    for i in range(a, b):
        for j in range(i+1, b+1):
            x.append((i*j)%2019)
    print(min(x))
### BUGGY CODE ###

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

n = b if n > b else n
ans = 0
for x in range(n, 0, -1):
    if x > b:
        continue
    ans = max(a * x // b - a * (x // b), ans)

print(ans)

### FIXED CODE ###

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

x = min(n, b-1)
ans = a * x // b - a * (x // b)

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

from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

S = str(input())

N = 13

dp =[0]*N
dp[0]=1

mul = 1
for i in reversed(range(0,len(S))):
    nextDP = [0]*N
    if S[i] == '?':
        # print('test')
        # print(mul)
        for k in range(10):
            for j in range(N):
                nextDP[(mul*k+j)%N] += dp[j]
                nextDP[(mul*k+j)%N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(mul*k+j)%N] += dp[j]
            nextDP[(mul*k+j)%N] %= MOD

    mul *= 10
    mul %= N
    dp = nextDP[:]
print(dp[5])


### FIXED CODE ###

#from enum import Enum
#from queue import Queue
#import collections

#import sys
#import math
#import time

#t1=time.time()
#input = sys.stdin.readline
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


S = input().strip()
# S = str('?'*(10**5))
N = 13

dp =[0]*N
dp[0]=1

mul = 1
reversed_S = S[::-1]
for c in reversed_S:
    nextDP = [0]*N
    if c == '?':
        # print('test')
        # print(mul)
        for k in range(10):
            for j in range(N):
                nextDP[(mul*k+j)%N] += dp[j]
                nextDP[(mul*k+j)%N] %= MOD
    else:
        k = int(c)
        for j in range(N):
            nextDP[(mul*k+j)%N] += dp[j]
            nextDP[(mul*k+j)%N] %= MOD

    mul *= 10
    mul %= N
    dp = nextDP[:]
print(dp[5])
#print(time.time()-t1)
### BUGGY CODE ###

n = int(input())

yn=1
a=2
while True:
    if n==yn:
        print('Yes')
        break
    elif yn>n:
        print('No')
        exit()
    else:
        yn+=a
        a+=1

a-=1

s=[[a] for i in range(n*2//a)]

l = [0]*n

for i in range(a):
    s[0].append(i+1)
    l[i]+=1

for i in range(1,n*2//a):
    for k in range(i):
        for j in range(a):
            if l[s[i-k-1][j+1]-1]==1:
                s[i].append(s[i-k-1][j+1])
                l[s[i-k-1][j+1]-1]+=1
                break
    while len(s[i]) - 1 != s[i][0]:
        for m in range(n):
            if l[m] == 0:
                s[i].append(m + 1)
                l[m] += 1
                if len(s[i]) - 1 == s[i][0]:
                        break
        if len(s[i]) - 1 != s[i][0]:
            for m in range(n):
                if l[m] == 1:
                    s[i].append(m + 1)
                    l[m] += 1
                    if len(s[i]) - 1 == s[i][0]:
                        break
        break

print(len(s))

for i in range(len(s)):
    for j in range(len(s[i])):
        if j==len(s[i])-1:
            print(s[i][j])
        else:
            print(s[i][j], end=' ')

### FIXED CODE ###

n = int(input())

yn=1
a=2
while True:
    if n==yn:
        print('Yes')
        break
    elif yn>n:
        print('No')
        exit()
    else:
        yn+=a
        a+=1

a-=1
k=n*2//a
s=[[a] for i in range(k)]

l = [0]*n

for i in range(a):
    s[0].append(i+1)
    l[i]+=1

for i in range(1,k):
    for j in range(i):
        s[i].append(s[j][i])
    while len(s[i]) - 1 != s[i][0]:
        for m in range(s[i-1][-1]-1,n):
            if l[m] == 0:
                s[i].append(m + 1)
                l[m] += 1
                if len(s[i]) - 1 == s[i][0]:
                        break
        if len(s[i]) - 1 != s[i][0]:
            for m in range(s[i-1][-1]-1,n):
                if l[m] == 1:
                    s[i].append(m + 1)
                    l[m] += 1
                    if len(s[i]) - 1 == s[i][0]:
                        break
        break

print(k)

for i in range(len(s)):
    for j in range(len(s[i])):
        if j==len(s[i])-1:
            print(s[i][j])
        else:
            print(s[i][j], end=' ')
### BUGGY CODE ###

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)


#"""
#h=10**4
#n=10**3
#ma=[[i,i+1] for i in range(n)]

#ma=sorted(ma,key=lambda x:x[1])
#ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print(dp[-1][-1])

### FIXED CODE ###

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print(dp[-1][-1])
### BUGGY CODE ###

import heapq
def cost(a, b, c, d):
    return min(abs(a-c), abs(b-d))

N = int(input())
T = []
for i in range(N):
    x, y = map(int, input().split())
    if (x, y) not in T:
        T.append((x, y))
lenT = len(T)
Tx, Ty = sorted(T, key = lambda t:t[0]), sorted(T, key = lambda t:t[1])
P = [[] for i in range(lenT)]
for i in range(lenT-1):
    xc, yc = cost(Tx[i][0], Tx[i][1], Tx[i+1][0], Tx[i+1][1]), cost(Ty[i][0], Ty[i][1], Ty[i+1][0], Ty[i+1][1])
    P[T.index(Tx[i])].append([xc, T.index(Tx[i+1])])
    P[T.index(Tx[i+1])].append([xc, T.index(Tx[i])])
    P[T.index(Ty[i])].append([yc, T.index(Ty[i+1])])
    P[T.index(Ty[i+1])].append([yc, T.index(Ty[i])])

Visit = [False for i in range(lenT)]
Visit[0] = True
Q = [p for p in P[0]]
heapq.heapify(Q)
Total = 0
while Q:
    nextCost, nextNode = heapq.heappop(Q)
    if Visit[nextNode] == False:
        Total += nextCost
        Visit[nextNode] = True
        for t in P[nextNode]:
            if Visit[t[1]] == False:
                heapq.heappush(Q, [t[0], t[1]])
print(Total)

### FIXED CODE ###

import sys
from operator import itemgetter
import heapq

def solve():
    input = sys.stdin.readline
    N = int(input())
    town = dict()
    road = [None] * N
    roadx, roady = [None] * N, [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        town[(x, y, i)] = i
        road[i] = (x, y, i)
        roadx[i] = (x, y, i)
        roady[i] = (x, y, i)
    roadx.sort()
    roadx_id = dict()
    roady.sort(key = itemgetter(1))
    roady_id = dict()
    for i in range(N):
        roadx_id[roadx[i]] = i
        roady_id[roady[i]] = i

    visited = [False] * N
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, 0)) #(cost, town_id)
    cost = 0
    while q:
        add_cost, id = heapq.heappop(q)
        #print(add_cost, id, cost)
        #print(visited)
        if not visited[id]:
            cost += add_cost
            visited[id] = True
            for s in range(2):
                nx = roadx_id[road[id]] + (-1) ** s #roadxにおけるid
                if 0 <= nx < N:
                    if not visited[town[roadx[nx]]]: heapq.heappush(q, (min(abs(road[id][0] - roadx[nx][0]), abs(road[id][1] - roadx[nx][1])), town[roadx[nx]]))
                
                ny = roady_id[road[id]] + (-1) ** s #roadyにおけるid
                if 0 <= ny < N:
                    if not visited[town[roady[ny]]]: heapq.heappush(q, (min(abs(road[id][1] - roady[ny][1]), abs(road[id][1] - roady[ny][1])), town[roady[ny]]))
    
    print(cost)

    return 0

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


def main():
    n, k = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    u = []
    v = []
    for i in range(n-k+1):
        u.append(sum(p[i:i+k]))
    x = u.index(max(u))
    for i in range(k):
        v.append(p[x+i])
    a=0
    for i in range(k):
        a += 1+0.5*(v[i]-1)
    print(a)


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n, k = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    u = [0]
    v = []
    w = []
    for i in range(n):
        u.append(u[i]+p[i])
    for i in range(n-k+1):
        w.append(u[k+i]-u[i])
    x = w.index(max(w))
    for i in range(k):
        v.append(p[x+i])
    a=0
    for i in range(k):
        a += 1+0.5*(v[i]-1)
    print(a)

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

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1       
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = 10**18 + 1
        
print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###

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

dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      dp[i]=min(dp[i],dp[i-num-1]+abs(h[i]-h[i-num-1]))
 
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])
### BUGGY CODE ###

import math
n=int(input())
l=[i for i in range(n+1)]
for i in range(2,int(math.sqrt(n))+1):
  if l[i]==i:
    for j in range(2,int(n/i)+1):
      if l[i*j]==i*j:
        l[i*j]=i

def time(n,r,c,ans):
  lc=l[c]
  if lc==1:
    return ans*(n+1)
  elif r==lc:
    return time(n+1,r,c//r,ans)
  else:
    return time(1,lc,c//lc,ans*(n+1))
ans=0
for i in range(1,n+1):
  t=time(0,0,i,1)
  ans+=i*t
print(ans)

### FIXED CODE ###

import math
n=int(input())
ans=0
for i in range(1,n+1):
  ans+=(i+(n//i)*i)*(n//i)//2
print(ans)
### BUGGY CODE ###

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[j] - h[i]) for j in range(max(i - k, 0), i))
print(dp[n-1])

### FIXED CODE ###

def main():
    n, k = [int(e) for e in input().split()]
    h = [int(e) for e in input().split()]
    dp = [0] * n
    for i in range(1, n):
        dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
    print(dp[n-1])
main()
### BUGGY CODE ###

N,M =map(int,input().split())
H = list(map(int,input().split()))
ab = [map(int, input().split()) for _ in range(M)]
a, b = map(list, zip(*ab))

cnt = 0

for i in range(1,N+1):
  Boolean = True
  # aの中からiから続く道があるかを全件検索
  for j in range(len(a)):
    # aの中にiがあり、その道先の展望台の山が高かったらiは破棄して次へ
    if ((i == a[j] and H[i-1] <= H[b[j]-1]) or (i == b[j] and H[i-1] <= H[a[j]-1])):
      Boolean = False
      break

  # abを全件調査してセーフだった場合にcntをあげる
  if(Boolean):
    cnt += 1
print(cnt)

### FIXED CODE ###

N,M =map(int,input().split())
H = list(map(int,input().split()))
ab = [map(int, input().split()) for _ in range(M)]
a, b = map(list, zip(*ab))

cnt = 0
removeList = []

for i in range(len(a)):
  if (H[a[i]-1] > H[b[i]-1]):
    removeList.append(b[i])
  elif (H[a[i]-1] < H[b[i]-1]):
    removeList.append(a[i])
  else:
    removeList.append(a[i])
    removeList.append(b[i])

set(removeList)
print(N - len(set(removeList)))
### BUGGY CODE ###

input()
a=list(map(int,input().split()))
s=1
for i in a:
    s*=i
print(s if s<=10**18 else -1)

### FIXED CODE ###

input()
a=list(map(int,input().split()))
a=a[::-1]
s=1
if 0 in a:
    print(0)
else:
    for i in a:
        s*=i
        if s>10**18:
            print(-1)
            break
    else:
        print(s)
### BUGGY CODE ###

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

for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        break

print(A, B)



### FIXED CODE ###

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

a = A - K
k = K - A
if k <= 0:
    k = 0
b = B - k

if a <= 0:
    a = 0
if b <= 0:
    b = 0

print(a, b)