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

import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.insert(0, 0)
    b.insert(0, 0)
    ans = 0
    at = 0
    for i in range(n+1):
        at += a[i]
        bt = at
        for j in range(m+1):
            if bt + b[j] > k:
                break
            bt += b[j]
            ans = max(ans, i+j)
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

INF = 10**11


def main(input, print):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    at = [0] * (n+1)
    bt = [0] * (m+1)
    for i in range(1, n+1):
        at[i] = at[i-1]+a[i-1]
    for i in range(1, m+1):
        bt[i] = bt[i-1]+b[i-1]

    ans = 0
    j = m
    for i in range(n+1):
        if at[i] > k:
            break
        while k < at[i] + bt[j]:
            j -= 1
        ans = max(ans, i+j)

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i,j in itertools.product(range(n+2), range(n+2)):
    if i>=j:
        continue
    tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
    g[i].append((tmp,j))
    g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

n, k = map(int, sys.stdin.readline().split())
w = [int(sys.stdin.readline()) for _ in range(n)]

wsum = sum(w)

P = max(int(math.ceil(wsum / k)), max(w))

while not loadable(w, n, k, P, wsum):
    P += 1
print(P)

### FIXED CODE ###

import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

n, k = map(int, sys.stdin.readline().split())
w = [int(sys.stdin.readline()) for _ in range(n)]

wsum = sum(w)

p = max(int(math.ceil(wsum / k)), max(w))
pre_f = p -1
pre_s = None

while True:
    if loadable(w, n, k, p, wsum):
        pre_s = p
    else:
        pre_f = p

    if pre_s != None and pre_s - pre_f == 1:
            break
    
    if pre_s:
        p = int((pre_s + pre_f) / 2)
    else:
        p = math.ceil(p * 1.01)
    
print(pre_s)
### BUGGY CODE ###

n = int(input())

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

ans = [a[0]]
double = []

for i in range(1, n):
    flag = True
    for j in ans:
        if a[i] == j:
            double.append(j)
            flag = False
            break
        if a[i] % j == 0:
            flag = False
            break
    if flag:
        ans.append(a[i])

for k in double:
    if k in ans:
        ans.remove(k)
print(len(ans))


### FIXED CODE ###

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

b = [True for i in range(a[-1]+1)]

ans = 0

for i, j in enumerate(a):
    if b[j]:
        t = 1
        while j*t < len(b):
            b[j*t] = False
            t += 1
        
        if i == n-1:
            ans += 1
        elif j != a[i+1]:
            ans += 1
        
print(ans)
### BUGGY CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=['' for _ in range(m+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[j+1]=dp[j]+s[i]
    else:dp[j+1]=max(dp[j+1],dp[j],key=len)
print(dp[-1])

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j]+1
    else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i+1][j+1])
ans=''
while n*m:
  if s[n-1]==t[m-1]:
    ans+=s[n-1]
    n-=1
    m-=1
  else:
    if dp[n-1][m]>dp[n][m-1]:n-=1
    else:m-=1
print(ans[::-1])
### BUGGY CODE ###

# D
a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

def route(start, mid, end):
    return abs(start-mid) + abs(mid-end)

for i in range(q):
    ans = 10000000000000000000000000
    # jinja
    j_list = [jin-x[i] for jin in s if (jin-x[i])<= 0]
    if len(j_list) != 0:
        j_w = j_list[-1] + x[i]
        t_list = [ter-j_w for ter in t if ter-j_w<=0]
        if len(t_list) != 0:
            t_w = t_list[-1] + j_w
            ans = min(route(x[i], j_w,t_w), ans)
        t_list = [ter-j_w for ter in t if ter-j_w>0]
        if len(t_list) != 0:
            t_e = t_list[0] + j_w
            ans = min(route(x[i], j_w,t_e), ans)
    j_list = [jin-x[i] for jin in s if (jin-x[i]) > 0]
    if len(j_list) != 0:
        j_e = j_list[0] + x[i]
        t_list = [ter-j_e for ter in t if ter-j_e <= 0]
        if len(t_list) != 0:
            t_w = t_list[-1] + j_e
            ans = min(route(x[i], j_e,t_w), ans)
        t_list = [ter-j_e for ter in t if ter-j_e > 0]
        if len(t_list) != 0:
            t_e = t_list[0] + j_e
            ans = min(route(x[i], j_e,t_e), ans)

    t_list = [ter-x[i] for ter in t if ter-x[i]<=0]
    if len(t_list) != 0:
        t_w = t_list[-1] + x[i]
        j_list = [jin-t_w for jin in s if jin-t_w<=0]
        if len(j_list) != 0:
            j_w = j_list[-1] + t_w
            ans = min(route(x[i], t_w,j_w), ans)
        j_list = [jin-t_w for jin in s if jin-t_w>0]
        if len(j_list) != 0:
            j_e = j_list[0] + t_w
            ans = min(route(x[i], t_w,j_e), ans)
    t_list = [ter-x[i] for ter in t if ter-x[i]>0]
    if len(t_list) != 0:
        t_e = t_list[0] + x[i]
        j_list = [jin-t_e for jin in s if jin-t_e<=0]
        if len(j_list) != 0:
            j_w = j_list[-1] + t_e
            ans = min(route(x[i], t_e,j_w), ans)
        j_list = [jin-t_e for jin in s if jin-t_e>0]
        if len(j_list) != 0:
            j_e = j_list[0] + t_e
            ans = min(route(x[i], t_e,j_e), ans)
    print(ans)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

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

for i in range(M):
    B, C = map(int, input().split())
    for j in range(B):
        if li[0] > C:
            break
        li[0] = C
        li.sort()
print(sum(li))


### FIXED CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC.sort(key=lambda x: -x[1])

for B, C in BC:
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
            break
print(sum(heap))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

P = []
before_a = False
for i in range(N):
  if before_a and S[i] == 'C':
    P.append(i)
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
for i in range(Q):
  ans = 0
  for num in P:
    if num >= LR[i][0] and num <= LR[i][1]-1:
      ans += 1
    elif num > LR[i][1]-1:
      break
  print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

P = [0] * (N)
before_a = False
cnt = 0
for i in range(N):
  if before_a and S[i] == 'C':
    cnt += 1
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
  P[i] = cnt
for i in range(Q):
  print(P[LR[i][1]-1] - P[LR[i][0]-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

x = 2019
S = input()
l = len(S)

a, b = [],[0]
for i in range(l):
#    a.append(int(S[:i+1]) % x)
#    if S[i] != '0':
    b.append(int(S[i:]) % x)

ans = 0

xx = [0 for _ in range(2019)]
for i in range(len(b)):
    xx[b[i]] += 1

def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 2019

S = input()
l = len(S)
#S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod
#    b.append(s % x)
    xx[s] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

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

N = int(input())
A = [int(x) for x in input().split()]
l = []
ans = 0
for i in range(N):
    l.append(A.count(i+1))
for j in l:
    ans += int(j*(j-1)/2)
for k in range(N):
    print(ans - l[A[k]-1] + 1)    


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
l = [0]*N
ans = 0
for a in A:
    l[a-1] += 1
for j in l:
    ans += int(j*(j-1)/2)
for k in range(N):
    print(ans - l[A[k]-1] + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
tmp = 1
beki = []
while tmp < 2*10**9:
	tmp *= 2
	beki.append(tmp)

ans = 0
for i in range(N):
	for j in range(i+1, N):
		if A[i]+A[j] in beki:
			ans += 1
			A[j] = 10**10
			break
print(ans)


### FIXED CODE ###

import bisect

def binum(num):
	number_len = len(bin(num))-2
	f = 2**number_len -1
	return (num^f)+1

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

while len(A) > 0:
	k = A.pop()
	if len(A) == 0:
		break
	if int(k) != k:
		continue
	x = binum(k)
	if x > A[-1]:
		continue
	if A[bisect.bisect_left(A,x)] == x:
		A[bisect.bisect_left(A,x)] -= 0.5
		cnt += 1

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

# -*- coding: utf-8 -*-
h,n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
a = [i[0] for i in ab]
b = [i[1] for i in ab]

from math import ceil
dp = [[0] * (h + 1) for _ in range(n)]

for j in range(h+1):
    dp[0][j] = ceil(j/a[0]) * b[0]

for i in range(1,n):
    for j in range(h+1):
        if j - a[i] > 0:
            dp[i][j] = min(dp[i][j-a[i]] + b[i],dp[i-1][j])
        else:
            dp[i][j] = min(b[i],dp[i-1][j])

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

### FIXED CODE ###

# -*- coding: utf-8 -*-
h,n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
a = [i[0] for i in ab]
b = [i[1] for i in ab]
 
from math import ceil
dp = [[0] * (h + 1) for _ in range(n)]
 
for j in range(h+1):
    dp[0][j] = ceil(j/a[0]) * b[0]
 
for i in range(1,n):
    for j in range(h+1):
        if j - a[i] > 0:
            dp[i][j] = min(dp[i][j-a[i]] + b[i],dp[i-1][j])
        else:
            dp[i][j] = min(b[i],dp[i-1][j])
 
print(dp[n-1][h])
### BUGGY CODE ###

# coding: utf-8
X,Y,A,B,C=map(int,input().split())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
R=list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

EP=[]
EQ=[]

for i in range(X):
    EP.append(P[i])
    
for i in range(Y):
    EQ.append(Q[i])

EP.sort()
EQ.sort()

while R[0]>EP[0] or R[0]>EQ[0]:
    if EP[0]<EQ[0]:
        EP.pop(0)
        EP.append(R.pop(0))
    else:
        EQ.pop(0)
        EQ.append(R.pop(0))
        
    if not(R):
        break

print(sum(EP)+sum(EQ))




### FIXED CODE ###

# coding: utf-8
X,Y,A,B,C=map(int,input().split())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
R=list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

EP=P[0:X]
EQ=Q[0:Y]

    # for i in range(X):
    #     EP.append(P[i])
        
    # for i in range(Y):
    #     EQ.append(Q[i])

EP.reverse()
EQ.reverse()

ans=sum(EP)+sum(EQ)

p=0
q=0

INF=10**12

EP.append(INF)
EQ.append(INF)

for i in range(C):
    if R[i]>EP[p] or R[i]>EQ[q]:
        if EP[p]<EQ[q]:
            ans+=R[i]
            ans-=EP[p]
            p+=1
        else:
            ans+=R[i]
            ans-=EQ[q]
            q+=1
    else:
        break

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

# coding: utf-8
# Your code here!

import bisect
import copy

N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))
A = sorted(A)
ori_A = copy.copy(A)
maisu = [0] * N

for i in range(M):
    _, b, c = A.pop(), ori_A.pop(), maisu.pop()
    a = b // 2 ** (c + 1)
    idx = bisect.bisect_right(A, a)
    A.insert(idx, a)
    ori_A.insert(idx, b)
    maisu.insert(idx, c + 1)
    
print(sum(A))
    

### FIXED CODE ###

# coding: utf-8
# Your code here!

import heapq

N, M = map(int, input().rstrip().split())
A = list(map(lambda x: -int(x), input().rstrip().split()))
heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    a = a / 2
    heapq.heappush(A, a)
    
print(sum([-int(x) for x in A]))
### BUGGY CODE ###

from collections import Counter

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

    for i in range(N):
        cnt = 0

        c=Counter(A[:i]+A[i+1:])
        values,counts=zip(*c.most_common())
        for j in counts:
            if j>=2:
                cnt+=j*(j-1)//2
        print(cnt)



resolve()

### FIXED CODE ###

from collections import Counter

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

    ans=0
    c = Counter(A)
    values, counts = zip(*c.most_common())
    for j in counts:
        if j >= 2:
            ans += j * (j - 1) // 2

    for i in A:
        if c[i]>=3:
            print(ans-(c[i]*(c[i]-1)//2-(c[i]-1)*(c[i]-2)//2))
        elif c[i]==2:
            print(ans-1)
        else:
            print(ans)






resolve()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
ans = sum(a)
many =[0]*(10**5)
bc = [0]*q
for i in range(10**5) :
    many[i] = a.count(i+1)

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

for i in range(q) : 
    ans += (bc[i][1] - bc[i][0]) * many[bc[i][0] - 1]
    print(ans)
    many[bc[i][1]-1] += many[bc[i][0]-1]
    many[bc[i][0]-1] =0



### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
q = int(input())
ans = sum(A)
many =[0]*(10**5 + 1)
for a in A :
    many[a] += 1

for i in range(q) : 
    B,C = (int(a) for a in input().split())
    many[C] += many[B]
    ans += many[B] * (C-B)
    many[B] = 0
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May 26 12:16:54 2018
DPL-1A
@author: maezawa
"""

n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)
dp = [[float('inf') for _ in range(n+1)] for _ in range(m+1)]
dp[m][0] = 0
#print(n,m)
#print(c)
#print(*dp, sep='\n')

def min_number(i,nn):
    if i == m:
        return dp[i][nn]
    if dp[i][nn] != float('inf'):
        return dp[i][nn]
    if nn < c[i]:
        dp[i][nn] = min_number(i+1,nn)
    else:
        temp = []
        j = 0
        while nn >= j*c[i]:
            temp.append(min_number(i+1, nn-j*c[i])+j)
            j += 1
        dp[i][nn] = min(temp)
    return dp[i][nn]

print(min_number(0,n))


### FIXED CODE ###

n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
    
dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = min([dp[i - c[j]]+1 for j in range(m) if i-c[j]>=0])

print(dp[n])
### BUGGY CODE ###

from bisect import bisect_left

x = int(input())
kouho = [pow(i, 5) for i in range(10 ** 7)]

for left in range(10 ** 7):
    L = pow(left, 5)
    kouho1 = abs(L + x)
    pos1 = bisect_left(kouho, kouho1)
    if pos1 < 10 ** 7:
        if kouho[pos1] == kouho1:
            right = pos1
            break
    kouho2 = abs(L - x)
    pos2 = bisect_left(kouho, kouho2)
    if kouho[pos2] < 10 ** 7:
        if kouho[pos2] == kouho2:
            right = pos2
            break

bigger = max(abs(left), abs(right))
smaller = min(abs(right), abs(left))
if smaller == 0:
    print(bigger, smaller)
    exit()
if bigger ** 5 - smaller ** 5 == x:
    print(bigger, smaller)
if bigger ** 5 + smaller ** 5 == x:
    print(bigger, -smaller)


### FIXED CODE ###

x = int(input())
for a in range(1000 + 1):
    for b in range(1000 + 1):
        A = pow(a, 5)
        B = pow(b, 5)
        if A - B == x:
            print(a, b)
            exit()
        if A + B == x:
            print(a, -b)
            exit()
print("wrong")
### BUGGY CODE ###

n = int(input())
s = list(sorted(input()) for i in range(n)) 

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
S = list(input() for i in range(n)) 

ctr = Counter()
ans = 0
for s in S:
    s =  ''.join(sorted(list(s)))
    if s in ctr:
        ans += ctr[s]
    ctr[s] += 1 

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

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

# print(*V,sep='\n',end='\n\n')

dp = [[[0]*(3+1) for _ in range(C+1)] for _ in range(R+1)]

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

for i in range(R+1):
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][k])
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][k] + V[i][j])

            if j-1 >= 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k-1 >= 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + V[i][j])

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

print(max(dp[R][C]))


### FIXED CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))
### BUGGY CODE ###

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

    c = [10**9] * N
    c[0] = 0
    for i in range(1, N):
        k = min(i, K)
        for j in range(1, k+1):
            c[i] = min(c[i], abs(h[i] - h[i-j]) + c[i-j])
            # print('i={}, c[i]={}'.format(i, c[i]))

    print(c[-1])


##########
if __name__ == "__main__":
    b_frog2()


### FIXED CODE ###

import numpy as np


def b_frog2():
    N, K = map(int, input().split())
    h = np.array(list(map(int, input().split())))

    c = np.zeros(N, dtype=int)
    c[0] = 0
    for i in range(1, N):
        j = max(0, i-K)
        c[i] = np.min(abs(h[i] - h[j:i]) + c[j:i])

    print(c[-1])


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

import copy

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

N = 13
MOD = 10 ** 9 + 7

s = input()
rs = reversed(s)

dp = [0 for i in range(N)]
dp[0] = 1

for i, si in enumerate(rs):
    nextdp = [0 for i in range(N)]
    r = 10 ** i % N

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = copy.copy(nextdp)

print(dp[5])


### FIXED CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
import bisect
i=0
for i in range(m):
    if bc[i][1]>a[0]:
        k=min(bc[i][0],bisect.bisect_left(a,bc[i][1]))
        a[:k]=[bc[i][1]]*k
        a.sort()
    else:
        break
print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)