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

import collections

n = int(input())
s = []
for _ in range(n):
    s.append(input())

pop_times = collections.Counter(s)
most_common_word = []

for i in pop_times.most_common():
    if pop_times.most_common()[0][1] == i[1]:
        most_common_word.append(i[0])

sorted_most_common_word = sorted(most_common_word)

for x in sorted_most_common_word:
    print(x)


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}
ans = []

for st in s:
    d[st] = d.get(st, 0) + 1

t = max(d.values())
ans_append = ans.append

for x in d:
    if d[x] == t:
        ans_append(x)

ans = sorted(ans)
for x in ans:
    print(x)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for q in range(K):
    foo = [1 for k in range(3*N+1)]
    for k in range(N):
        for j in range(1, A[k]+1):
            foo[k-j+N] +=1
            foo[k+j+N] +=1
    #print(foo)

    for k in range(N):
        A[k] = foo[k+N]
    #print(A)

ans = ""
for k in range(len(A)):
    ans += str(A[k]) + " "

print(ans.rstrip())

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
foo = [[0 for k in range(N)] for k in range(42)]
for k in range(len(A)):
    foo[0][k] = A[k]
if K <42:
    for q in range(K):
        unko = [0 for k in range(N)]
        for k in range(N):
            if k + foo[q][k]+1 < N:
                unko[k + foo[q][k]+1] -=1
            unko[max(k - foo[q][k], 0)] +=1
        unchi = 0
        for k in range(N):
            unchi += unko[k]
            foo[q+1][k] = unchi
        #print(unko)
        #print(foo[q+1])
        count =0
        for l in range(N):
            if foo[q+1][l] < N:
                break
            else:
                count +=1
        
        if count == N:
            break
        
                        
        #print(foo)
    print(" ".join(map(str, foo[q+1])))

     
else:
    print((str(N)+" ")*(N-1)+str(N))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 50)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 50)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

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

N = int(input())
count = 0
for X in range(N):
    for i in range(1, int(X**0.5)+1):
        if X % i == 0:
            count += 1
            if i != X // i:
                count += 1
print(count)
  

### FIXED CODE ###

N = int(input())
ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
### BUGGY CODE ###

N,K=map(int, input().split())
import numpy as np
a_ls=np.array(list(map(int, input().split())))


t=1
track=[]
while not(t in set(track)):
	track+=[t]
	t=a_ls[t-1]

#print(track)
#print(t)
#print(track.index(t)) #dokokara loop ga hajimaruka

if track.index(t)>K:
	print(track[K])
else:
	s=(K-track.index(t))%(len(track)-track.index(t))
	print(track[s+track.index(t)])



### FIXED CODE ###

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

j=1
step=0
s=set([])
l=[]
loop_s=-1
loop_g=-1

while True:
	s.add(j)
	l+=[j]
	j=a_ls[j-1] #update
	if j in s:
		loop_s=l.index(j)
		loop_g=len(l)
		break


#print(l)
#print(loop_s)
#print(loop_g)

if K<loop_s:
	print(l[K])
elif (K+1-loop_s)%(loop_g-loop_s)!=0:
	print(l[loop_s+(K+1-loop_s)%(loop_g-loop_s)-1])
else:
	print(l[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
c = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    c[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
c = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    c[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)
### BUGGY CODE ###

from collections import deque
s = input()
que = deque(list(s))
q = int(input())
for _ in range(q):
    l = input()
    if l[0] == "1":
        s = s[::-1]
        que  = deque(list(s))
    else:
        if l[2] == "1":
            que.appendleft(l[4])
        else:
            que.append(l[4])
        s = list(que)
print("".join(s))

### FIXED CODE ###

from collections import deque
s = input()
que = deque(list(s))
q = int(input())
flag = True
for _ in range(q):
    l = input()
    if flag:
        if l[0] == "1":
            flag = False
        else:
            if l[2] == "1":
                que.appendleft(l[4])
            else:
                que.append(l[4])
    else:
        if l[0] == "1":
            flag = True
        else:
            if l[2] == "1":
                que.append(l[4])
            else:
                que.appendleft(l[4])
if flag:
    ans = list(que)
    print("".join(ans))
else:
    ans = list(que)[::-1]
    print("".join(ans))
### BUGGY CODE ###

import math

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

a = sorted(list(map(int,input().split())),reverse=True)

for _ in range(m):
    #print(a)
    a[0] = a[0]/2
    i = 0
    #print("->{}".format(a))
    while i<n-1:
        if a[i]<a[i+1]:
            a[i],a[i+1] = a[i+1],a[i]
            i+=1
        else:
            break
    #print("->->{}".format(a))

a = list(map(math.floor,a))
#print()
#print(a)

print(sum(a))

### FIXED CODE ###

import math
import heapq

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

a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

for _ in range(m):
    max = heapq.heappop(a)
    max = max/2
    heapq.heappush(a,max)

a = list(map(lambda x:x*(-1),a))
a = list(map(math.floor,a))

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

def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bitm - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bitp + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

### FIXED CODE ###

def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt1 = 0
  if x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str,input().split())) for i in range(Q)]
for i in range(Q):
    if(Query[i][0] == "1"):
        S = S[::-1]
    else:
        if(Query[i][1] == "1"):
            S = Query[i][2] + S
        else:
            S = S + Query[i][2]
            
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str,input().split())) for i in range(Q)]
front = ""
back = ""
hanten_flag = 0
cnt = 0
for i in range(Q):
    if(Query[i][0] == "1"):
        hanten_flag ^= 1
    else:
        if(Query[i][1] == "1" and hanten_flag == 0):
            front = Query[i][2] + front
        elif(Query[i][1] == "1" and hanten_flag == 1):
            back = back + Query[i][2]
        elif(Query[i][1] == "2" and hanten_flag == 0):
            back = back + Query[i][2]
        else:
            front = Query[i][2] + front
SS = front + S + back
if(hanten_flag == 1):
    SS = SS[::-1]
print(SS)
### BUGGY CODE ###

def resolve():
    def counts(x):
        tot = 0
        for i in range(N):
            if A[i] < 0:
                l, r = -1, N
                while r-l > 1:
                    c = (l+r)//2
                    if A[c]*A[i] < x:
                        r = c
                    else:
                        l = c
                tot += N - r
            else:
                l, r = -1, N
                while r-l > 1:
                    c = (l + r) // 2
                    if A[c] * A[i] < x:
                        l = c
                    else:
                        r = c
                tot += r
            if A[i] * A[i] < x:
                tot -= 1
        tot //= 2
        return tot < K
 
 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
 
    l = -(10**18)
    r = 10**18
    while r-l > 1:
        x = (l + r) // 2
        if counts(x):
            l = x
        else:
            r = x
    print(l)
 
 
if __name__ == "__main__":
    resolve()

### FIXED CODE ###


import numpy as np
def resolve():
    n, k = map(int, input().split())
    a = np.array(input().split(), dtype=np.int64)
    a.sort()

    zero = np.count_nonzero(a == 0)
    positive = a[a > 0]
    negative = a[a < 0]

    def count(x):  # 積が x 以下のペアは何個あるか？
        ans = 0
        if x >= 0:  # 片側が 0 の場合
            ans += n * zero
        ans += np.searchsorted(a, x // positive, side="right").sum()  # 片側が正の場合
        ans += n * len(negative) - np.searchsorted(a, -(-x // negative), side="left").sum()  # 片側が負の場合 切り上げは -(-a//b)
        ans -= np.count_nonzero(a * a <= x)  # 同じもの2つは選べない
        return ans // 2

    ok = 10 ** 18
    ng = -ok - 1
    while ok - ng > 1:  # 二分探索
        cen = (ok + ng) // 2
        if count(cen) >= k:
            ok = cen
        else:
            ng = cen
    print(ok)

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



def p(k,w,maxP):
    count = 1
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
    
    if count > k :
        result = False
    else:
        result = True

    return result, count, mP

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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = 1000000000
rangeMin = 1

while _:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid)[0] == False and p(k,w,rangeMid+1)[0] == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid)[0] == True and p(k,w,rangeMid+1)[0] == True:
        rangeMax = rangeMid
    else:
        break

print(p(k,w,rangeMid+1)[2])

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

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

L = []

cnt_sum = 0
# for i in range(M):
#     cnt = BC[i][0]
#     for j in range(N):
#         if cnt_sum <= N:
#             L.append(BC[i][1])
#             cnt_sum += 1
#             cnt -= 1
#         elif L[j] < BC[i][1]:
#             L[j] = BC[i][1]
#             cnt -= 1
#         if cnt <= 0:
#             break
for i in range(M):
    for j in range(BC[i][0]):
        L.append(BC[i][1])
L.sort(reverse=True)
A.sort()
ans = sum(A)
LL = len(L)
for k in range(N):
    if k <= LL-1 and L[k] > A[k]:
        ans += (L[k] - A[k])
    else:
        break
print(ans)


### FIXED CODE ###

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

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

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

n,l,T = map(int,input().split())
s = [0 for i in range(n)]
for i in range(n):
    s[i] = list(map(int, input().split()))

def f(w):
    if w == 1:
        return 1
    elif w == 2:
        return -1
    

d=[0 for i in range(n)]
for i in range(n-1):
    d[i] = s[i+1][0] - s[i][0]
d[n-1] = s[0][0] + l - s[n-1][0]

t = 0
dt = 0.5
while t < T:
    t+= dt
    s[0][0] = s[0][0] + f(s[0][1])*dt
    if s[0][0] >= l:
        s[0][0] -= l
    elif s[0][0] < 0:
        s[0][0] += l
        
    for i in range(n):
        if i < n-1:
            d[i] = d[i] + f(s[i+1][1])*dt - f(s[i][1])*dt
            s[i+1][0] = s[i][0] + d[i]
            if s[i+1][0] >= l:
                s[i+1][0] -= l
        else:
            d[n-1] = d[n-1] + f(s[0][1])*dt - f(s[n-1][1])*dt
            
    for i in range(n):
        if d[i] == 0 and i < n-1:
            s[i+1][1], s[i][1] = s[i][1], s[i+1][1]
        elif i == n-1 and d[i] == 0 :
            s[0][1], s[n-1][1] = s[n-1][1], s[0][1]
            
import math
for i in range(n):
    print(math.floor(s[i][0]))
    

### FIXED CODE ###

from math import floor
n,l,t = map(int,input().split())
ants = []
touch = 0

for i in range(n):
    x, w = map(int,input().split())
    if w == 1:
        touch += (x + t) // l
        x1 = (x + t) % l
    else:
        touch += (x - t) // l
        x1 = (x - t) % l
    ants.append(x1)
touch = touch % n
ants.sort()
ants = ants[touch:]+ants[:touch]

for i in range(n):
    print(ants[i])
### BUGGY CODE ###

import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ava = [1]*n
    for i in range(n):
        for j in range(i+1,n):
            if i==j:    continue
            if ava[i]:
                if not a[i]%a[j]:
                    ava[i] = 0
            if ava[j]:
                if not a[j]%a[i]:
                    ava[j] = 0
    print(ava.count(1))
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys

def solve(a,n):
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]:
            for i in range(2*rep,m,rep):
                ava[i] += 2
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))
### BUGGY CODE ###

N= int(input())
A = list(map(int, input().split()))
B=[0]*N
C=0
for i in range(N):
    C+=B[A[i]-1]
    B[A[i]-1]+=1
for i in range(N):
    print(int(C-(A.count(A[i]))+1))

### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline

n = int(input())
s = input()

ls_password = []

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            pw = s[i] + s[j] + s[k]
            ls_password.append(pw)

# print(ls_password)

print(len(set(ls_password)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input()

count = 0

ls_si = []
for i in range(n-2):
    # print("i={}".format(i))
    if s[i] in ls_si:
        pass
    else:
        ls_si.append(s[i])
        ls_sj = []
        for j in range(i+1,n-1):
            if s[j] in ls_sj:
                pass
            else:
                ls_sj.append(s[j])
                # ls = s[j+1:-1]
                # st = set(ls)
                # l = len(st)
                # print(ls)
                # print(st)
                # print(l)
                count += len(set(list(s[j+1:-1])))

# print(ls_si)
# print(ls_sj)
print(count)
### BUGGY CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)

### FIXED CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)
### BUGGY CODE ###

from collections import*
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
grid=defaultdict(str)
for i in range(w+2):
    grid[(0,i)]="#"
    grid[(h+1,i)]="#"
for i in range(h):
    for k,v in enumerate(input()):
        grid[(i+1,k+1)]=v
for i in range(1,h+1):
    grid[(i,0)]="#"
    grid[(i,w+1)]="#"
#for i in range(h+2):
#    print(*[grid[(i,j)]for j in range(w+2)])

stack=deque()
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[(y,x)]=="#":
            grid[(y,x)]=str(0)
            stack.append((y,x))

for i in range(h*w):
    tmp=deque()
    while stack:
        #print(stack)
        my,mx=stack.pop()
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[(my+y,mx+x)]==".":
                grid[(my+y,mx+x)]=str(i+1)
                tmp.append((my+y,mx+x))
    stack=tmp
    if len(tmp)==0:
        print(i)
        break


### FIXED CODE ###

from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#")for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            stack.append((y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                tmp.append([my+y,mx+x])
    stack=tmp
    if len(tmp)==0:
        print(i)
        break
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
from heapq import heapify, heappop, heappush


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    heapify(a)

    for _ in range(m):
        b, c = map(int, input().split())
        for _ in range(b):
            ai = heappop(a)
            if ai < c:
                heappush(a, c)
            else:
                heappush(a, ai)
                break

    print(sum(a))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from heapq import heapify, heappop, heappush


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda x: -x[1])
    heapify(a)

    for i in range(m):
        b, c = bc[i]
        for _ in range(b):
            ai = heappop(a)
            if ai < c:
                heappush(a, c)
            else:
                heappush(a, ai)
                break

    print(sum(a))


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

N = int(input())
S = input()
answer = 0

for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            if (j-i) != (k-j):
                if S[i-1] != S[j-1] and S[i-1] != S[k-1] and S[j-1] != S[k-1]:
                    answer += 1

print(answer)

### FIXED CODE ###

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

ans = S.count('R')*S.count('G')*S.count('B')

for i in range(N-2):
  for j in range(i+1,N-1):
    k = 2*j-i
    
    if k >= N:
      break
    
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      ans -= 1
      
print(ans)