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

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    A = B[:]
    if sum(A) == N**2:
        break
ans = ''
for a in A:
    ans += str(a) + ' '
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)
### BUGGY CODE ###

import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[(2,0),(2,1),(2,2),(2,-1),(2,-2),(1,-2),(1,2),(0,2),(0,-2),(-1,2),(-1,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2)]
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False
while len(cand)>0:
    #print(cand)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
    for each in wap:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
            dis[h1][w1]=cost+1
            cand.append((h1,w1,cost+1))
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

### FIXED CODE ###

import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
Es=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[]
for i in range(-2,3):
    for j in range(-2,3):
        wap.append((i,j))
wap.remove((0,0))
for each in walk:
    wap.remove(each)
cand=[start]
dis[start[0]][start[1]]=0
flag=False
edge=[]
while len(cand)>0:
    #print(dis)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
        elif h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==1 and Es[hh][ww]>cost:
            Es[hh][ww]=cost
            edge.append((hh,ww,cost))
            #print(edge)
    if len(cand)==0:
        for place in edge:
            hh,ww,cost=place
            for each in wap:
                h1,w1=hh+each[0],ww+each[1]
                #print(h1,w1)
                if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                    dis[h1][w1]=cost+1
                    cand.append((h1,w1,cost+1))
        edge=[]
        #print(cand)
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
li = list(map(int,input().split()))

for i in range(n):
    new_list = []
    Sum = 0
    if i == 0:
        new_list = li[1:n]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    elif i == n-1:
        new_list = li[:n-1]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    else:
        new_list = li[:i] + li[i+1:]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
li = list(map(int,input().split()))
S=Counter(li)
Sum = 0
for k in range(n):
            if S[k+1] > 1:
                Sum += (S[k+1] * (S[k+1] -1)) / 2
            else:
                continue

#k個目が何なのかを考える
for i in range(n):
    if S[li[i]] > 1:
        Sum_2 = Sum
        Sum_2 = Sum_2 - (S[li[i]] * (S[li[i]] -1)) / 2 + ((S[li[i]]-1) * (S[li[i]] -2)) / 2
        print(int(Sum_2))
    else:
        print(int(Sum))
### BUGGY CODE ###

from sys import stdin
import fractions

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

point = 0

for i in li:
    lin = prime_factorize(i)
    point += lin.count(2)

print(point)

### FIXED CODE ###

from sys import stdin
import fractions

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

point = 0

for i in li:
    lin = prime_factorize(i)
    point += lin.count(2)

print(point)
### BUGGY CODE ###

N = int(input())
A = list(map(int,(input().split())))
b = [0]*N
for i in range(N):
    b[i] = format(A[i],"b")
one = [[0]*20 for _ in range(N)]
for i in range(N):
    for j in range(20):
        if j < len(list(b[i])):
            one[i][j] = int(b[i][-(j+1)])

sumone = [[0]*20 for _ in range(N+1)]
for j in range(20):
    for i in range(1,N+1):
        sumone[i][j] = sumone[i-1][j] + one[i-1][j]
sumone.append([2]*20)

def ok(l,r):
    for j in range(20):
        if sumone[r][j] - sumone[l][j] >= 2:
            return False
    else:
        return True

ans = 0
r = 0
for l in range(N+1):
    flag = 0
    while r < N+2 and ok(l,r) and flag == 0:
        if r != N+1:
            r += 1
        else:
            flag = 1
            break
    ans += r-l-1

print(ans)  

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

ans = 0
r = 0
sum = 0
xor = 0
for l in range(N):
    while r < N and sum+A[r] == xor^A[r]:
        sum += A[r]
        xor ^= A[r]
        r += 1
    sum -= A[l]
    xor ^= A[l]
    ans += r-l

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

import fractions
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans=ans+fractions.gcd(i,fractions.gcd(j,l))
print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans=ans+gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

N=int(input())
ABC=[]
for i in range(N):
  l=list(map(int,input().split()))
  ABC=ABC+[l]
dp=[[0,0,0] for i in range(N)]#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
for i in range(3):
  dp[0][i]=ABC[0][i]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+ABC[i][1],dp[i-1][0]+ABC[i][1])
  dp[i][0]=max(dp[i-1][1]+ABC[i][0],dp[i-1][2]+ABC[i][0])
  dp[i][2]=max(dp[i-1][1]+ABC[i][2],dp[i-1][0]+ABC[i][2])
ans=max(dp[N-1])
print(ans)

### FIXED CODE ###

N=int(input())
A=[]
B=[]
C=[]
for i in range(N):
  l1,l2,l3=map(int,input().split())
  A+=[l1]
  B+=[l2]
  C+=[l3]
dp=[[0,0,0] for i in range(N)]#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
dp[0][0]=A[0]
dp[0][1]=B[0]
dp[0][2]=C[0]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+B[i],dp[i-1][0]+B[i])
  dp[i][0]=max(dp[i-1][1]+A[i],dp[i-1][2]+A[i])
  dp[i][2]=max(dp[i-1][1]+C[i],dp[i-1][0]+C[i])
ans=max(dp[N-1])
print(ans)
### BUGGY CODE ###

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個
def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  res = [INF for _ in range(n+1)] #道が0本からn本
  for s in range(1<<n): #選ばれたものを全探索
    p = [0] #最初の大通り
    for i in range(n):
      if (s>>i)&1 == 1: #bitが立っている位置は道があるので追加
        p.append(A[i][0])
    now = 0 #現在の移動距離
    for i in range(n): #i個目の町に注目
      m = INF
      for j in range(len(p)): #すべての道に対して愚直に最短距離を求める。
        m = min(m,abs(p[j]-A[i][0]))
      now += m*A[i][1] #最短距離×人数
    b = len(p) -1 #道を何本追加したか。1を引くのは最初の大通り。
    res[b] = min(res[b],now)
  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

### FIXED CODE ###

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n):
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      now = 0
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)
### BUGGY CODE ###

A,B,C,K = map(int, input().split())
now = K
sum = 0

for i in range(A):
  if now == 0:
    break
  sum += 1 
  now = now - 1

if now != 0:
  for i in range(B):
    if now == 0:
      break
    now = now - 1
    
if now != 0:    
  for i in range(C):
    if now == 0:
      break
    sum -= 1
    now = now - 1
    
print(sum)

### FIXED CODE ###

A,B,C,K = map(int, input().split())
now = K
sum = 0

if A < K:
  now -= A
  sum += A
  if B < now:
    now -= B
    print(sum - now)
  else:
    print(sum)
else:
  print(K)
### BUGGY CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  AB = [ab[1] for ab in AB for i in range(ab[0])]
  
  index = min([N, len(AB)])
  result = 0
  for i in range(index):
    if AB[i] < C[i]:
      index = i
      break
    result += AB[i]
  
  if index < N:
    result += sum(C[index:])
  print(result)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  
  result = 0
  i, j = 0, 0
  while i < N:
    A, B = AB[j] if j < M else (0, 0)
    j += 1
    if i+A < N and B >= C[i+A]:
      i += A
      result += A * B
    else:
      break
    
  while i < N:
    if C[i] > B:
      result += sum(C[i:])
      break
    else:
      result += B
      A -= 1      
      if j < M and A == 0:
        A, B = AB[j] if j < M else (0, 0)
        j += 1
    
    i += 1
  
  print(result)

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

argN = int(input())
argS = input()
aryS = list(argS)

idxBorder = 0
ansMin = 1000000

ans1 = aryS.count(".") #全て黒にする場合
ans2 = aryS.count("#") #全て白にする場合

for i in range(1,argN):
  #cntW1 = aryS[:i].count(".")
  cntB1 = aryS[:i].count("#")

  cntW2 = aryS[i:].count(".")
  #cntB2 = aryS[i:].count("#")
  #print(str(i) + "," + str(cntB1) + "," + str(cntW2))
  ansMin = min(ansMin,cntB1 + cntW2)

print(min(ans1,ans2,ansMin))

### FIXED CODE ###

argN = int(input())
aryS = list(input())

cnt = aryS.count(".") 
ans = cnt
for i in range(argN):
  if aryS[i] == ".":
    cnt -= 1
  elif aryS[i] == "#":
    cnt += 1

  if ans > cnt:
    ans = cnt

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

N = int(input())
S = list(input())
import itertools
print(len(set(list(itertools.combinations(S,3)))))

### FIXED CODE ###

N = int(input())
S100 = input()
S100list = list(S100)
X100 = set(S100list)
PIN = 0
for i in X100:
    S10 = S100[S100.find(i)+1:]
    X10 = set(list(S10))
    for j in X10:
        S1 = S10[S10.find(j)+1:]
        X1 = set(list(S1))
        PIN += len(X1)
    
print(PIN)
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
count = 0
next = 0
for i in range(len(L)):
  if L[next] == 2:
    print(count+1)
    quit()
  next = L[next]-1
  count += 1
print(-1)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

n,m = map(int,input().split())
a_list = list(map(int,input().split()))
for i in range(m):
  a_list.sort(reverse=True)
  a_list[0] = a_list[0]//2
print(sum(a_list))


### FIXED CODE ###

n,m = map(int,input().split())
import math
a_list = list(map(int,input().split()))
for i in range(n):
  a_list[i] = -1 * a_list[i]
import heapq
heapq.heapify(a_list)
for j in range(m):
  
  a = heapq.heappop(a_list)
  a = math.ceil(a/2)
  heapq.heappush(a_list,a)


print(-1 * sum(a_list))
### BUGGY CODE ###


import itertools
def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for _ in range(M):
    P.append(list(map(int,input().split())))
for m in range(M):
    P_X[P[m][0]]+=1
for m in range(M):
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in range(M):
    if P[k][0] in max_X and P[k][1] in max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

    



### FIXED CODE ###


def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  P_X[k[0]] == Max_X and P_Y[k [1]] == Max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)
### BUGGY CODE ###

n,y = map(int,input().split())

ans = 0
for i in range(1000):
    if ans != 0:
        break
    else:
        for j in range(1000):
            for k in range(1000):
                if (i + k + j)== n and (10000*i + 5000*j + 1000*k) == y:
                    print(i,j,k)
                    ans +=1
                else:
                    continue
                
if ans == 0:
    print('-1','-1','-1')

### FIXED CODE ###

n,y = map(int,input().split())

ans = 0
for i in range(2001):
    if ans != 0:
        break
    else:
        for j in range(2001-i):
            if (10000*i + 5000*j + 1000*(n-(i + j))) == y and ((n-(i + j)) >=0):       
                print(i,j,n-(i + j))
                ans +=1
            else:
                continue
                
if ans == 0:
    print('-1','-1','-1')
### BUGGY CODE ###

import sys

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

ans = a[0]
for i in range(1, N):
    ans *= a[i]

if ans > 1000000000000000000:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

import sys

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

for val in a:
    if val == 0:
        print("0")
        exit(0)

ans = 1
for val in a:
    ans *= val
    if ans > 1000000000000000000:
        print("-1")
        exit(0)

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = TA[0][0]
vote_A = TA[0][1]
if len(TA)>1:
	for Ti, Ai in TA[1:]:
		n = 1
		tmp_Ti = Ti * n
		tmp_Ai = Ai * n
		while tmp_Ti < vote_T or tmp_Ai < vote_A:
			n += 1
			tmp_Ti = Ti * n
			tmp_Ai = Ai * n
		vote_T = tmp_Ti
		vote_A = tmp_Ai
print(vote_A + vote_T)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = 1
vote_A = 1
for x, y in TA:
	# n = max(ceil(vote_T/x),ceil(vote_A/y))
	# n = max(-(-vote_T // x), -(-vote_A // y))
	n = max((vote_T//x + (vote_T%x!=0)),vote_A//y + (vote_A%y!=0))
	vote_T = x * n
	vote_A = y * n
print(vote_A + vote_T)
### BUGGY CODE ###

from collections import defaultdict
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=defaultdict(int)
a.sort()

for i in range(m):
    b,c=map(int,input().split())
    d[c]+=b

d_sorted=sorted(d.items(),reverse=True, key=lambda x:x[0])
l=[]

for i,j in d_sorted:
    for k in range(j):
        l.append(i)
    if len(l)>=n:
        break

for i in range(min(n, len(l))):
    a[i]=max(a[i],l[i])

print(sum(a))

### FIXED CODE ###

from collections import defaultdict
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=defaultdict(int)
a.sort()

for i in range(m):
    b,c=map(int,input().split())
    d[c]+=b

d_sorted=sorted(d.items(),reverse=True, key=lambda x:x[0])
l=[]

for i,j in d_sorted:
    for k in range(j):
        l.append(i)
        if len(l)>n:
            break
    else:
        continue
    break
for i in range(min(n, len(l))):
    a[i]=max(a[i],l[i])

print(sum(a))
### BUGGY CODE ###

s = input()
q_num = int(input())
for i in range(q_num):
    q = tuple(input().split())
    if q[0] == '1':
        s = s[::-1]
    else:
        if q[1] == '1':
            s = q[2] + s 
        else:
            s += q[2]
print(s)

### FIXED CODE ###

s = input()
q_num = int(input())
head = []
tail = []
flip = 0
for i in range(q_num):
    q = tuple(input().split())
    if q[0] == '1':
        flip ^= 1
    else:
        f = int(q[1]) - 1
        c = q[2]
        if f ^ flip == 0:
            head.append(c)
        else:
            tail.append(c)
if flip:
    head, tail = tail, head
    s = s[::-1]
head = ''.join(head)
tail = ''.join(tail)
print(head[::-1] + s + tail)
### BUGGY CODE ###

n,k = map(int,input().split())
h=sorted(list(int(input()) for i in range(n)))
h+=h
mi=float('inf')
ansma=0
ansmi=0
for i in range(int(len(h)/2)):
    tmp=h[i:i+k]
    tmpma=max(tmp)
    tmpmi=min(tmp)
    if mi > tmpma - tmpmi:
        mi=tmpma-tmpmi
        ansma=tmpma
        ansmi=tmpmi

print(ansma-ansmi)

### FIXED CODE ###

n,k = map(int,input().split())
h=list(int(input()) for i in range(n))
h.sort()
mi=float('inf')

for i in range(n-k+1):
    mi = min(mi, h[i+k-1]-h[i])
 
print(mi)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

maxdig = 60

ans = 0
for i in range(60+1):
  d = 2**i
  cnt1 = 0
  for a in A:
    if (a >> i) & 1:
      cnt1 += 1
  ans += (cnt1*(N-cnt1)*d)
  ans = ans%1000000007

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

maxdig = 60
mod = 10**9+7

ans = 0
for i in range(60+1):
  cnt1 = sum([1 for a in A if (a >> i) & 1])
  ans += (cnt1*(N-cnt1)*(1<<i))
  ans = ans%mod

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

N, K = map(int, input().split())
a = list(map(int, input().split()))
A = []
Index = 0

def getRate(list, int1, int2):
    value = 1
    for i in range(int1, int2):
        value = value * list[i]
    return value



for i in range(N-K+1):
    A.append(getRate(a, i, K + i))

ans = []

for i in range(len(A)-1):
    if A[i] < A[i+1]:
        ans.append("Yes")
    else:
        ans.append("No")

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

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

ans = []
flag = 1
for i in range(N):
    if a[i] < a[i + K]:
        print('Yes')
    else:
        print("No")
    flag += 1
    if flag == N-K+1:
        break
### BUGGY CODE ###

x = raw_input().split()
a,op,b = x[0],x[1],x[2]
while 1:
	if op == "+":
		print a+b
	elif op == "-":
		print a-b
	elif op == "/":
		print a/b
	elif op == "*":
		print a*b
	else:
		break

### FIXED CODE ###

while 1:
	x = raw_input().split()
	a,op,b = int(x[0]),x[1],int(x[2])
	if op == "+":
		print a+b
	elif op == "-":
		print a-b
	elif op == "/":
		print a/b
	elif op == "*":
		print a*b
	else:
		break
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
seta = set(a)
dic = {}
for i in seta:
  dic[i] = a.count(i)

dic = sorted(dic.items(), key=lambda x:x[1])
typeCnt = len(seta) - k
cnt = 0
if typeCnt > 0:
  for i in range(typeCnt):
    cnt = cnt + dic[i][1]

print(cnt)

### FIXED CODE ###

n, k = map(int, input().split())
d = {}
for i in input().split():
  if i in d:
    d[i] = d[i] + 1 
  else:
    d[i] = 1

l = sorted(d.values())
print(sum(l[:len(l) - k]))