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

n,m = map(int, input().split())
a = list(map(int,input().split()))
idx = 0
for i in range(m):
    b,c = map(int, input().split())
    a += [c]*b
    idx += b
a.sort()
print(sum(a[idx:]))

### FIXED CODE ###

from heapq import heappop, heappush


n,m = map(int,input().split())
A = list(map(int,input().split()))
pq = []
ans = 0

for a in A:
    heappush(pq, [-a, 1])
    
for _ in range(m):
    b,c = map(int,input().split())
    heappush(pq, [-c, b])

for i in range(n):
    c,b = heappop(pq)
    c = -c
    ans += c
    if b > 1:
        b -= 1
        heappush(pq, [-c, b])
        
print(ans)
### BUGGY CODE ###

from sys import stdin
X = (stdin.readline().rstrip())
for i in range(10**6):
    X = X.replace("ST","")
print(len(X))

### FIXED CODE ###

from sys import stdin
from collections import deque
X = (stdin.readline().rstrip())
stack = []
for i in X:
    if i == "S":
        stack.append(i)
    elif (i == "T" and stack == []):
        stack.append(i)
    elif (i == "T" and stack[-1] == "S"):
        stack.pop()
    else:
        stack.append(i)
print(len(stack))
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A_sub = A.copy()
A_sub.sort(reverse=True)
#print(A)

for i in range(N):
    # print(A[i])
    A_sub2 = A_sub.copy()
    A_sub2.remove(A[i])
    print(A_sub2[0])
    


### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A_sub = A.copy()
MAX = max(A)
A_sub.remove(MAX)
MAX2 = max(A_sub)

for i in range(N):
    if A[i] < MAX:
        print(MAX)
    elif A[i] == MAX:
        print(MAX2)
### BUGGY CODE ###

n = int(input())
x = 1
y = 1
for i in range(n):
    t, a = [int(_) for _ in input().split()]
    tt = t
    aa = a
    while tt < x or aa < y:
        tt += t
        aa += a
    x = tt
    y = aa
print(x+y)

### FIXED CODE ###

# import math
n = int(input())
x = 1
y = 1
for i in range(n):
    t, a = [int(_) for _ in input().split()]
    if x%t == 0:
        kt = x//t
    else:
        kt = x//t + 1
    if y % a == 0:
        ka = y // a
    else:
        ka = y // a + 1

    k = max(kt, ka)
    x = t*k
    y = a*k

print(x+y)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
  R,C,K=map(int, input().split())
  M=[[0 for i in range(C)]for i in range(R)]
  for i in range(K):
    r,c,v=map(int, input().split())
    r-=1
    c-=1
    M[r][c]=v
  dp=[[[0]*(4) for j in range(C)] for i in range(R)]
  dp[0][0][1]+=M[0][0]
  for r in range(R):
    for c in range(C):
      if 0<r:
        dp[r][c][1]=max(max(dp[r-1][c])+M[r][c],dp[r][c][1])
        dp[r][c][0]=max(max(dp[r-1][c]),dp[r][c][0])
      if 0<c:
        dp[r][c][3]=max(dp[r][c-1][2]+M[r][c],dp[r][c][3],dp[r][c-1][3])
        dp[r][c][2]=max(dp[r][c-1][1]+M[r][c],dp[r][c][2],dp[r][c-1][2])
        dp[r][c][1]=max(dp[r][c-1][0]+M[r][c],dp[r][c][1],dp[r][c-1][1])
        dp[r][c][0]=max(dp[r][c-1][0],dp[r][c][0])
  print(max(dp[-1][-1]))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  R,C,K=map(int, input().split())
  M=[[0 for i in range(C)]for i in range(R)]
  for i in range(K):
    r,c,v=map(int, input().split())
    r-=1
    c-=1
    M[r][c]=v
  dp0=[[0 for j in range(C)] for i in range(R)]
  dp1=[[0 for j in range(C)] for i in range(R)]
  dp2=[[0 for j in range(C)] for i in range(R)]
  dp3=[[0 for j in range(C)] for i in range(R)]
  dp1[0][0]+=M[0][0]
  for r in range(R):
    for c in range(C):
      if 0<r:
        dp1[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c])+M[r][c],dp1[r][c])
        dp0[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c]),dp0[r][c])
      if 0<c:
        dp3[r][c]=max(dp2[r][c-1]+M[r][c],dp3[r][c],dp3[r][c-1])
        dp2[r][c]=max(dp1[r][c-1]+M[r][c],dp2[r][c],dp2[r][c-1])
        dp1[r][c]=max(dp0[r][c-1]+M[r][c],dp1[r][c],dp1[r][c-1])
        dp0[r][c]=max(dp0[r][c-1],dp0[r][c])
  ans=0
  for i in range(R):
    for j in range(C):
      ans=max(ans,dp1[i][j],dp2[i][j],dp3[i][j])
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
clist = list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)
clist.sort(reverse=True)

ablist = []
for i in alist:
  for j in blist:
      ablist.append(i+j)
      
ablist.sort(reverse=True)
ablist = ablist[0:K]

abclist = []
for ij in ablist:
  for k in clist:
    abclist.append(ij+k)
    
abclist.sort(reverse=True)
for ijk in range(K):
  print(abclist[ijk])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
clist = list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)
clist.sort(reverse=True)

ablist = []
for i in alist:
  for j in blist:
      ablist.append(i+j)
      
ablist.sort(reverse=True)
ablist = ablist[0:K]

abclist = []
for ij in ablist:
  for k in clist:
    abclist.append(ij+k)
    
abclist.sort(reverse=True)
for ijk in range(K):
  print(abclist[ijk])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
def main():
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[]
  for i in range(q):
    l,r=map(int,input().split())
    queries.append((r-1,l-1,i))
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[n]*n
  bitt=BinaryIndexedTree(n+1)
  j=0
  for i in range(n):
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k:
                ans_+=1
                ll=[0]*h
            else:
                j+=1
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        flag=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k and flag==0:
                flag=1
                ans_+=1
                ll=[0]*h
            elif max(ll)>k and flag==1:
                ans_=10**5
                break
            else:
                j+=1
                flag=0
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
operation = []

for _ in range(M):
    t = tuple(map(int, input().split()))
    operation.append(t)

operation.sort(key=lambda x: x[1], reverse=True)

for i in range(M):
    A.sort()
    if operation[i][1] <= A[0]:
        break
    else:
        for j in range(operation[i][0]):
            if operation[i][1] > A[j]:
                A[j] = operation[i][1]
            else:
                break

print(sum(A))


### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
A = list(map(int, input().split()))
operation = []
ans = 0

for _ in range(M):
    t = tuple(map(int, input().split()))
    operation.append(t)

operation.sort(key=lambda x: x[1], reverse=True)
A.sort()
A = deque(A)
operation = deque(operation)

while A and operation:
    if A[-1] >= operation[0][1]:
        ans += A[-1]
        A.pop()
    else:
        cnt = 0
        for i in range(operation[0][0]):
            if len(A) == i or A[i] > operation[0][1]:
                cnt = i
                break
        else:
            cnt = operation[0][0]
        for _ in range(cnt):
            A.popleft()
        ans += cnt * operation[0][1]
        operation.popleft()

ans += sum(A)

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

import numpy as np

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

a = np.array(a)
b = np.array(b)

if np.sum(a) < np.sum(b):
    ans = -1
else:
    diff = a - b
    diff_ori = np.copy(diff)
    dames= np.where(diff < 0)[0]
    for d in dames:
        yoyuu = np.argmax(diff)
        diff[yoyuu] += diff[d]
        diff[d] -= diff[d]
    ans = len(diff) - np.sum(diff_ori == diff)
print(ans)

### FIXED CODE ###

import numpy as np

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


a = np.array(a)
b = np.array(b)


if np.sum(a) < np.sum(b):
    ans = -1
else:

    diff = a - b
    diff = np.sort(diff)
    if np.sum(diff<0) == 0:
        ans = 0
    else:
        for ind in range(len(diff)):
            if diff[ind] > 0:
                break

        minus = np.sum(diff[:ind])
        minus_num = ind

        yoyuu = diff[ind:][::-1]

        for ind in range(len(yoyuu)):
            minus += yoyuu[ind]
            if minus > 0:
                ans = minus_num + ind + 1
                break
            if minus == 0:
                ans = minus_num + ind
                break

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

K, S = map(int, input().split())

ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans = ans + 1 

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(min(K,S)+1):
	for y in range(min(K,S)+1):
		if 0 <= S - x - y <= K:
			ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)



### FIXED CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

r = 10**9 + 7
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

p = n - k + 1

c = 1

ans = 0

for i in range(p, 0, -1):
    ans += (a[n-i] - a[i-1]) * c
    ans %= r
    c = c * (n-i + 1) // (p-i+1)

print(ans)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

a.sort()

pos = 0
neg = 0

for i in range(N - K + 1):
    pos += a[N - i - 1] * comb(N- i - 1, K - 1)
    pos %= mod
    neg += a[i] * comb(N- i - 1, K - 1)
    neg %= mod

ans = (pos - neg) % mod

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

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

for i in range(M):
  B, C = map(int, input().split())
  BC = [C] * B
  A.extend(BC)

print( sum(sorted(A, reverse=True)[:N]) )

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = [(A[i], 1) for i in range(N)]

for i in range(M):
  B, C = (map(int, input().split()))
  D.append((C, B))
  
D.sort()
D.reverse()

ans, left = 0, N
for (i, j) in D:
    use = min(j, left)
    ans += use * i
    left -= use
print(ans)
### BUGGY CODE ###

X = int(input())
b = 0.0
c = True

while c:
    if ((X + b**5)**0.2).is_integer():
        c = False
        a = int(((X + b**5)**0.2))
    elif b >= 0:
        b = -1*b
    else:
        b = -1*b + 1
        
print(a, int(b))

### FIXED CODE ###

X = int(input())

c = 1
result = False


while not result:
    for i in range(c):
        a = c -i
        b = i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        b = c - i
        a = - i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        a = -c+i
        b = -i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        a = i
        b = -c + i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    c += 1

print(A, B)
### BUGGY CODE ###

A, B = map(int, input().split())
k = 0

while True:
    if 2**(k-1) <= B < 2**k:
        break
    k += 1


def sum_xor(n):
    res = []
    for i in range(k):
        if i == 0:
            res.append(1) if n % 4 == 1 or n % 4 == 2 else res.append(0)
        else:
            nmod = n % (2 ** (i + 1))
            if (2**(i+1))/2 <= nmod < 2**(i+1) and nmod % 2 == 0:
                res.append(1)
            else:
                res.append(0)
    res.reverse()
    return res


ax = sum_xor(A-1)
bx = sum_xor(B)

ans = []
for j in range(k):
    ans.append(1) if (ax[j] + bx[j]) % 2 == 1 else ans.append(0)

ans = "".join(map(str, ans))
print(int(ans, 2))


### FIXED CODE ###

A, B = map(int, input().split())
k = 1

while True:
    if B == 0:
        break
    if 2**(k-1) <= B < 2**k:
        break
    k += 1


def sum_xor(n):
    res = []
    for i in range(k):
        if i == 0:
            res.append(1) if n % 4 == 1 or n % 4 == 2 else res.append(0)
        else:
            nmod = n % (2 ** (i + 1))
            if (2**(i+1))/2 <= nmod < 2**(i+1) and nmod % 2 == 0:
                res.append(1)
            else:
                res.append(0)
            # odd = [2**i+2*j for j in range(2**(i-1))]
            # tmp = n % 2**(i+1)
            # res.append(1) if tmp in odd else res.append(0)
    res.reverse()
    return res


ax = sum_xor(A-1)
bx = sum_xor(B)

ans = []
for j in range(k):
    ans.append(1) if (ax[j] + bx[j]) % 2 == 1 else ans.append(0)

ans = "".join(map(str, ans))
print(int(ans, 2))
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    s = min(p[:i+1])
    if p[i] <= s:
        ans += 1
        
print(ans)

### FIXED CODE ###

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

s = 10**18
ans = 0

for i in range(n):
    s = min(s, p[i])
    if p[i] <= s:
        ans += 1
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

count = []
for i in range(0,n-1):
    if s[i] == 'A' and s[i+1] == "C":
        count.append(i+1)


for slr in lr:
    l = slr[0]
    r = slr[1]
    res = [i for i in count if i >= l and i < r]

    print(len(res))




### FIXED CODE ###

import sys
from itertools import accumulate
input = sys.stdin.readline

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

count = [0]
for i in range(0,n-1):
    if s[i] == 'A' and s[i+1] == "C":
        count.append(1)
    else:
        count.append(0)
count.append(0)

flag = list(accumulate(count))

for slr in lr:
    l = slr[0]
    r = slr[1]
    print(flag[r-1] - flag[l-1])
### BUGGY CODE ###

def solve(N, M, fridens):
    parents = [-1 for _ in range(N)]
    groups = {}
    for x in range(N):
        groups[x] = [x]

    for A, B in friends:
        if B in groups:
            parents[B] = A
            groups[A].append(B)
            del groups[B]

    ans = len(max(groups.values(), key=len))
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    friends = []
    seen = []
    for _ in range(M):
        AB = sorted([x - 1 for x in map(int, input().split())])
        if AB not in seen:
            friends.append(AB)
            seen.append(AB)
    solve(N, M, friends)


### FIXED CODE ###

n, m = map(int, input().split())
par = list(range(n))


def find(x):
    while par[x] != x:
        par[x] = par[par[x]]
        x = par[x]
    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 1)]

for k in range(n):
    s[find(k)] += 1


print(max(s))
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 100
for i in range(0,len(s)):
    tmp = 0
    for j in range(0,len(s)):
        if j<i and s[j]=='W':
            tmp += 1
        elif j>i and s[j]=='E':
            tmp += 1
    ans = min(ans,tmp)
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = s.count('E')
r = 10**6
if s[0]=='E':
    ans -= 1

r = min(ans,r)

for i in range(1,n):
    if s[i-1]=='W' and s[i]=='W':
        ans += 1
    elif s[i-1]=='E' and s[i]=='E':
        ans -= 1
    r = min(ans,r)
print(r)
### BUGGY CODE ###

import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
"""
int(input())
map(int,input().split())
list(map(int,input().split()))
"""
# t=int(input())
t=1
for term in range(t):
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=[0 for i in range(n)]
    for i in range(1,n):
        B[i]=min(    (B[j]+abs(A[j]-A[i]) )   for j in range(i-1,max(i-k-1,-1),-1))
    print(B[n-1])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().strip()
 
def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
        # for j in range(max(0,i-k),i):
        #     dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])
 
    print (dp[-1])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if v not in visited:
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    d[a - 1].append(b - 1)
    d[b - 1].append(a - 1)

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

if Fennec > Snuke:
    print("Fennec")
else:
    print("Snuke")

### FIXED CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if tekazu[v] == float("inf"):
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    d[a - 1].append(b - 1)
    d[b - 1].append(a - 1)

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

if Fennec > Snuke:
    print("Fennec")
else:
    print("Snuke")
### BUGGY CODE ###

from operator import mul
from functools import reduce

def c(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

cnt = 0
s = []
tmp = []
n = int(input())
for i in range(n):
    string = input()
    string = ''.join(sorted(string))
    s.append(string)

for i, e in enumerate(s):
    """
    要素が何個あるか検査　AND　tmpにないやつ
    ・１：なにもしない
    ・2以上：個数調べてCNT更新。その要素をtmpに記録する
    """
    if s.count(e) > 1 and not e in tmp:
        cnt += c(s.count(e), 2)
        tmp.append(e)
print(cnt)

### FIXED CODE ###

import collections

cnt = 0
s = []
tmp = []
n = int(input())
for i in range(n):
    string = input()
    string = ''.join(sorted(string))
    s.append(string)

# for i, e in enumerate(s):
#     count = s.count(e)
#     if count > 1 and not e in tmp:
#         cnt += count*(count-1)//2
#         tmp.append(e)
cc = collections.Counter(s)

for cv in cc.values():
    if cv > 1:
        cnt += cv*(cv-1)//2

print(cnt)