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

N, K = map(int, input().split())
A = list(map(int, input().split()))
b = list(set(A))
if len(b) <= K:
  print(0)
else:
  q = []
  for i in range(len(b)):
    q.append(A.count(b[i]))
  q.sort(reverse=True)
  s = 0
  for i in range(K):
    s += q[i]
  print(N-s)


### FIXED CODE ###

import collections
N, K = map(int, input().split())
A = list(map(int, input().split()))
c = collections.Counter(A)
a = list(c.values())
if len(a) <= K:
  print(0)
else:
  a.sort(reverse=True)
  print(N-sum(a[:K]))
### BUGGY CODE ###


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

S = [0]

for i in A:
    S.append(S[-1] + i)

S.sort()

count = 0
for i,s in enumerate(S):
    for j in range(len(S)-i-1):
        if s == S[i+j+1]:
            count += 1
        else: break
    
print(count)

### FIXED CODE ###

from math import factorial
from collections import Counter

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

S = [0]

for i in A:
    S.append(S[-1] + i)

count = 0
count_dict = Counter(S)
for i in count_dict.values():
    if i == 1:
        continue
    count += factorial(i) // (factorial(i - 2) * factorial(2))
print(count)
### BUGGY CODE ###

import itertools

N = int(input())
L = input().split()

cand = itertools.combinations(L,3)

ans = 0
for c in cand:
    a, b, c = int(c[0]), int(c[1]), int(c[2])
    if a < b + c and b < a + c and c < a + b:
        ans += 1

print(ans)


### FIXED CODE ###

import itertools, bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        cindex = bisect.bisect_left(L, int(L[i]) + int(L[j]))
        ans += cindex-1 - j

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

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s) for s in input().split(' ')])
components = [set([i+1]) for i in range(N)]
inconvenience = []
totalNpair = N * (N-1) / 2
for i in range(M-1, -1, -1):
    convenience = 0
    a, b = bridges[i]
    for c in range(len(components)):
        convenience += len(components[c]) * (len(components[c])-1) / 2
        if a in components[c]:
            a_index = c
        if b in components[c]:
            b_index = c
    inconvenience.append(int(totalNpair - convenience))
    if a_index != b_index:
        a_set = components.pop(max(a_index, b_index))
        b_set = components.pop(min(a_index, b_index))
        components.append(a_set | b_set)
for i in range(M-1, -1, -1):
    print(inconvenience[i])



### FIXED CODE ###

def find_root(components, n):
    if components[n] == n:
        return n
    elif components[components[n]] == components[n]:
        return components[n]
    else:
        components[n] = find_root(components, components[n])
        return components[n]

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s)-1 for s in input().split(' ')])
components = [i for i in range(N)]
componentsLen = [1 for i in range(N)]
inconvenience = [int(N * (N-1) / 2)]
for i in range(M-1, -1, -1):
    a, b = bridges[i]
    a_root = find_root(components, a)
    b_root = find_root(components, b)
    if a_root != b_root:
        inconvenience.append(inconvenience[-1] - componentsLen[a_root] * componentsLen[b_root])
        if componentsLen[a_root] < componentsLen[b_root]:
            a_root, b_root = b_root, a_root
        componentsLen[a_root] += componentsLen[b_root]
        components[b_root] = a_root
    else:
        inconvenience.append(inconvenience[-1])
for i in range(M-1, -1, -1):
    print(inconvenience[i])
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="#":
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
ans=0
while que:
    y,x=map(int,que.popleft())
    ans=dist[y][x]
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(ans)


### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="#":
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
ans=0
while que:
    y,x=map(int,que.popleft())
    ans=dist[y][x]
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

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

n,*a=map(int,open(0).read().split())
for i in range(n):
    print(a.index(i+1)+1,end=' ')

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
b=[0]*n
for i in range(n):
    b[a[i]-1]=str(i+1)
print(' '.join(b))
### BUGGY CODE ###

# coding: utf-8
import sys
import random

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

def mkDivisors(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



def main():
    x = ni()
    xmod10 = x%10
    div = mkDivisors(x)
    random.shuffle(div)
    for i in div:
        for n in [i,-1*i]:
            if n%10 == xmod10:
                for b in range(-n-125, n+125):
                    a = b + n
                    if pow(a,5) - pow(b,5) == x:
                        print(a,b)
                        return
    print("Erorr")
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    x = ni()
    xmod10 = x%10
    for a in range(-125, 125):
        for b in range(-125, 125):
            if (a-b)%10 == xmod10:
                if pow(a,5) - pow(b,5) == x:
                    print(a,b)
                    return
    print("Erorr")
    return


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

import numpy as np
import sys

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline() for _ in range(n)],dtype='int64')


for i in range(n):
    if i==0:
        print(max(a[i+1:]))
    elif i==n-1:
        print(max(a[:i]))
    else:
        print(max(max(a[:i]),max(a[i+1:])))


### FIXED CODE ###

import numpy as np
import sys

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline() for _ in range(n)],dtype='int64')

ma=a.max()
ju=0
for i in range(n):
    if a[i]!=ma or ju==1:
        print(ma)
    else:
        if i==0:
            b=max(a[i+1:])
        elif i==n-1:
            b=max(a[:i])
        else:
            b=max(max(a[:i]),max(a[i+1:]))
        if ju==0:
            if b==ma:
                ju=1
            else:
                ju=-1
        print(b)
### BUGGY CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    abl = []
    cl = []
    for i in range(m):
        abl.append(list(map(int, input().rstrip('\n').split())))
        cl.append(list(map(int, input().rstrip('\n').split())))
    dp = [[set(), 0] for _ in range(2 ** m)]
    mt = 10 ** 20
    #各bitを総検索
    for i in range(2 ** m):
        bt = bin(i)
        #先頭bitに対して処理
        if i >= 1 and len(bt[2:]) - 1 < m:
            for c in cl[len(bt[2:])-1]:
                dp[i][0].add(c)
            dp[i][1] += abl[len(bt[2:])-1][0]
        #先頭bitより後ろのbitが同じパターンの解放済とコストを追加
        if i >= 2:
            for c in dp[int(bt[3:], 2)][0]:
                dp[i][0].add(c)
            dp[i][1] += dp[int(bt[3:], 2)][1]
        if len(dp[i][0]) == n:
            mt = min(mt, dp[i][1])
    print(mt if mt != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    pw = 2 ** n
    dp = [10 ** 20] * pw
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        c = sum(2 ** (i - 1) for i in list(map(int, input().rstrip('\n').split())))
        for j in range(pw):
            if dp[j | c] > dp[j] + a:
                dp[j | c] = dp[j] + a
    if dp[-1] == 10 ** 20:
        print(-1)
    else:
        print(dp[-1])


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

def comb(n, r):
    bunshi = 1
    for i in range(n-r+1,n+1):
        bunshi = bunshi*i
    bunbo = 1
    for i in range(1,r+1):
        bunbo = bunbo * i 
    return bunshi//bunbo

def pascal(n):
    c = [[0 for i in range(n+1)] for j in range(n+1)]
    c[0][0] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j == 0 or j == i:
                c[i][j] = 1
                continue
            c[i][j] = c[i-1][j-1] +c[i-1][j]
    return(c)

def nC2(n):
    c = [0 for _ in range(n)]
    c[0] = 1
    for i in range(1, n):
        c[i] = i+1 +c[i-1]
    return(c)

N = int(input())
A = list(map(int, input().split()))
# c = pascal(N)
nc2 = nC2(N)
duplication = {}
ans = 0
for x in A:
    if x in duplication:
        continue
    count = A.count(x)
    if count > 1:
        duplication[x] = count
        # ans += comb(count,2)
        ans += nc2[count-2]
for x in A:
    if x not in duplication:
        print(ans)
    else:
        # print(ans -comb(duplication[x],2) +comb(duplication[x]-1,2))
        print(ans -duplication[x]+1)
        # print(ans -c[duplication[x]][2] +c[duplication[x]-1][2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
def test():
    duplication = {}
    ans = 0
    for x in A:
        if x in duplication:
            continue
        count = A.count(x)
        if count > 1:
            duplication[x] = count
            ans += count*(count-1)//2
    for x in A:
        if x not in duplication:
            print(ans)
        else:
            print(ans -(duplication[x]-1))
from collections import defaultdict

sum = 0
count_dic = defaultdict(int)
for x in A:
    count_dic[x] +=1
for v in count_dic.values():
    sum += v*(v-1)//2
for x in A:
    print(sum -(count_dic[x]-1))
### BUGGY CODE ###

import random
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : 
    B = A[i:i+L]
    random.shuffle(B)
    ans.append(min(B))
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###


if __name__ == "__main__":
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    dp = [float("inf")]*len(arr)
    dp[0] = 0
    cost = 0
    for i in range(len(arr)):
        for jump in range(i+1,i+k+1):
            if(jump<len(arr)):
                dp[jump] = min(dp[jump],dp[i]+abs(arr[jump]-arr[i]))
    print(dp[-1]) 

### FIXED CODE ###


n,k = map(int,input().split())
arr = list(map(int,input().split()))
dp = [float("inf")]*len(arr)
dp[0] = 0
cost = 0
for i in range(len(arr)):
    for jump in range(i+1,i+k+1):
        if(jump<len(arr)):
            dp[jump] = min(dp[jump],dp[i]+abs(arr[jump]-arr[i]))
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
G = [[] for _ in range(n)]
indeg = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    G[r].append((l, d))
    indeg[r] += 1

from collections import deque
ng = False
for start, deg in enumerate(indeg):
    if deg == 0:
        continue
    st = deque([[start, 0]])
    visited_cost = [-1] * n
    while st:
        i, cost = st.pop()
        for ni, nd in G[i]:
            if visited_cost[ni] == -1 or visited_cost[ni] == cost + nd:
                # まだ記録されていない
                # 既に記録されていて、矛盾していない場合
                visited_cost[ni] = cost + nd
                st.append([ni, cost + nd])
            else:
                # 既に記録されていて、矛盾している場合
                # 終了
                ng = True
                break
        if ng:
            break
    if ng:
        break

print('No' if ng else 'Yes')


### FIXED CODE ###

n, m = map(int, input().split())
G = [[] for _ in range(n)]
indeg = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    G[l].append((r, d))
    G[r].append((l, -d))

from collections import deque
ng = False
visited = [0] * n
visited_cost = [0] * n

for start in range(n):
    if visited[start]:
        continue
    visited[start] = 1
    st = deque([[start, 0]])
    while st:
        i, cost = st.pop()
        for ni, nd in G[i]:
            if visited[ni] == 0:
                visited[ni] = 1
                visited_cost[ni] = cost + nd
                st.append([ni, cost + nd])
            else:
                # 既に記録されていて、矛盾している場合
                if visited_cost[ni] != cost + nd:
                    # 終了
                    ng = True
                    break
        if ng:
            break
    if ng:
        break
print('No' if ng else 'Yes')
### BUGGY CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])


### FIXED CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c
#print(tmp)

count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])
### BUGGY CODE ###

# %%

n, m = list(map(int, input().split()))
ary = sorted(list(map(int, input().split())), reverse=True)
bry = sorted(list(map(int, input().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):
        if (num in ary[i:]) & (num in bry[j:]):
            i += 1
            j += 1
        elif (num in ary[i:]) ^ (num in bry[j:]):
            if num in ary[i:]:
                cnt *= len([b for b in bry if num < b]) % mod
                i += 1
            else:
                cnt *= len([a for a in ary if num < a]) % mod
                j += 1
        else:
            nn = len([a for a in ary if num < a])
            nm = len([b for b in bry if num < b])
            cnt *= (nn * nm - (n * m - num)) % mod

    print(cnt % mod)


### FIXED CODE ###

import sys

# %%

n, m = list(map(int, sys.stdin.readline().split()))
ary = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
bry = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    ary.append(0)
    bry.append(0)

    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):

        if (num == ary[i]) and (num == bry[j]):
            i += 1
            j += 1

        elif (num == ary[i]) or (num == bry[j]):
            if num == ary[i]:
                cnt *= len(bry[:j])
                i += 1
            else:
                cnt *= len(ary[:i])
                j += 1

        else:
            # na = len(ary[:i])
            # nb = len(bry[:j])
            cnt *= (i * j - (n * m - num))

        cnt = cnt % mod

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

from collections import defaultdict
from itertools import combinations

N = int(input())
S = []
m = ['M', 'A', 'R', 'C', 'H']
c = defaultdict(int)
ans = 0

if N <= 2:
    print(0)
else:
    for i in range(N):
        na = input()
        fs = na[0]
        
        if fs in m and na not in S:
            S.append(na)
            
            if fs == 'M':
                c['M'] += 1
            elif fs == 'A':
                c['A'] += 1
            elif fs == 'R':
                c['R'] += 1
            elif fs == 'C':
                c['C'] += 1
            elif fs == 'H':
                c['H'] += 1
        
    con = list(combinations(m, 3))
    for i, j, k in con:
        ans += c[i] * c[j] * c[k]
    print(ans)

### FIXED CODE ###

import itertools
N = int(input())
M, A, R, C, H = 0, 0, 0, 0, 0
final_ans = 0
for i in range(N):
    a = input()
    if a[0] =='M':
        M += 1
    elif a[0] =='A':
        A += 1
    elif a[0] =='R':
        R += 1
    elif a[0] =='C':
        C += 1
    elif a[0] =='H':
        H += 1

MARCH = [M, A, R, C, H]
ans = list(itertools.combinations(MARCH,3))

final_ans = 0
for i in ans:
    final_ans += i[0]*i[1]*i[2]
print(final_ans)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
for b,c in ope:
    if len(d) == n:
        break
    elif len(d) + b > n:
        for i in range(n-b):
            d.append(c)
    else:
        for i in range(b):
            d.append(c)
d.reverse()
arr = sorted(arr,reverse = True)
x = [0]*(n+1)
x[0] = sum(arr)
for i in range(1,n+1):
    t_arr = arr.pop()
    if d:
        t_d = d.pop()
    else:
        t_d = t_arr
    x[i] = x[i-1] + t_d - t_arr
    if x[i] < x[i-1]:
        break
print(max(x))


### FIXED CODE ###

import bisect
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
i = 0
ok = True
for b,c in ope:
    for rep in range(b):
        if i >= n or arr[i] > c:
            ok = False
            break
        arr[i] = c
        i += 1
    if ok:
        continue
    else:
        break
print(sum(arr))
### BUGGY CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, k = nm()
h = nl()
h.insert(0, h[0])
INF = 10 ** 9
dp = [INF for _ in range(n + 1)]
dp[1] = 0

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if i + j <= n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
        else:
            break
print(dp[-1])


### FIXED CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, k = nm()
h = nl()
h.insert(0, h[0])
INF = 10 ** 9
dp = [INF for _ in range(n + 1)]
dp[1] = 0

for i in range(2, n + 1):
    x = max(i - k, 1)
    dp[i] = min([d + abs(h[i] - hd) for d, hd in zip(dp[x:i], h[x:i])])
print(dp[-1])
### BUGGY CODE ###

S = list(input())
Q = int(input())
reverse = 0
for i in range(Q):
    Query = input()
    T = int(Query[0])
    if T == 1:
        reverse += 1
    elif T == 2:
        F = int(Query[2])
        C = Query[4]
        if (F+reverse)%2 == 1:
            S.insert(0, C)
        elif (F+reverse)%2 == 0:
            S.append(C)

if reverse%2 == 1:
    S = S[::-1]


print(''.join(S))
print('\n')


### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')