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

import sys,gc

    
A=[]
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.insert(0,s[1])
    elif s[0] == 'delete':
        try:
            A.remove(s[1])
        except:
            pass
    elif s[0] == 'deleteFirst':
        A.pop(0)
    elif s[0] == 'deleteLast':
        A.pop()
    n -=1
    
for e in A:
    print int(e),

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # K = 200000
    # T = int(input())
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]
    # A = [0] * 100000

    for _ in range(K):
        AA = [1] * len(A)
        for i, ai in enumerate(A):
            for ii in range(ai):
                ii += 1
                if i + ii < len(A):
                    AA[i + ii] += 1
                if i - ii >= 0:
                    AA[i - ii] += 1
        A = AA
    print(' '.join([str(a) for a in A]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # T = int(input())
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    for _ in range(K):
        AA = [0] * len(A)
        for i, ai in enumerate(A):
            l = max(0, i - ai)
            r = min(N - 1, i + ai)
            AA[l] += 1
            if r != N - 1:
                AA[r + 1] -= 1
        for i in range(len(AA) - 1):
            AA[i + 1] += AA[i]

        A = AA
        flag = True
        for a in AA:
            if a != len(A):
                flag = False
                break
        if flag:
            break
    print(' '.join([str(a) for a in A]))


if __name__ == "__main__":
    main()
### 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(n-2):
    tmp=h[i:i+k]
    tmpma=max(tmp)
    tmpmi=min(tmp)
    if i == n:
        break
    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 ###

from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    n, m = map(int, next(inputs).split())
    an = list(map(int, next(inputs).split()))[:n]
    an.sort()
    bc = [ list(map(int, next(inputs).split())) for _ in range(m) ]
    bc.sort(key=lambda bc: bc[1]) # sort by c
    ans = 0
    for b, c in bc:
        for i in range(b):
            if an[i] < c:
                an[i] = c
                pass
            pass
        an.sort()
        pass
    return sum(an)


def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print(main(gen_inputs()))
    pass


### FIXED CODE ###

from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    n, m = map(int, next(inputs).split())
    an = list(map(int, next(inputs).split()))[:n]
    an.sort()
    bc = [ list(map(int, next(inputs).split())) for _ in range(m) ]
    bc.sort(key=lambda bc: bc[1], reverse=True) # sort by c
    
    x = 0
    y = 0
    ans = 0
    for i in range(n):
        if x < m and bc[x][1] >= an[i]:
            ans += bc[x][1]
            y += 1
            if y >= bc[x][0]:
                x += 1
                y = 0
                pass
            pass
        else:
            ans += an[i]
            pass
        pass
    return ans

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


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

k, s = map(int, input().split(" "))

count = 0
for x in range(k+1):
    for y in range(min(k, s-x)+1):
        for z in range(min(k, s-x-y)+1):
            if x+y+z == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split(" "))

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            count += 1

print(count)
### BUGGY CODE ###

def nCa(n,a,mod=10**9+7):
  p=q=1
  for i in range(a):
    p = p*(n-i)%mod
    q = q*(i+1)%mod
  return p*pow(q,mod-2,mod) %mod

def main():
  mod = 10**9+7
  n,k = map(int,input().split())
  
  ans = 1
  for i in range(1,min(k+1,n)):
    ans = (ans + nCa(n,i)*nCa(n-1,n-i-1)) % mod 
  
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

n,k = map(int,input().split())
P = 10**9+7

ans = 1
nCl = 1
n1Cl = 1
for l in range(1,min(k+1,n)):
    nCl = nCl*(n+1-l)*pow(l,P-2,P)%P
    n1Cl = n1Cl*(n-l)*pow(l,P-2,P)%P
    ans = (ans+nCl*n1Cl)%P

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

S = input()
Q = int(input())
reverse = 0
for i in range(Q):
    s = input().split()
    if int(s[0]) == 1:
        reverse = (reverse + 1) % 2
    else:
        if int(s[1]) == 1:
            if reverse == 1:
                S = S + s[2]
            else:
                S = s[2] + S
        else:
            if reverse == 1:
                S = s[2] + S
            else:
                S = S + s[2]

if reverse == 1:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

def main():
    from sys import stdin
    from collections import deque
    S = input()
    Q = int(input())
    reverse = 0
    head = []
    tail = []
    head_deque = deque(head)
    tail_deque = deque(tail)
    
    for _ in [0] * Q:
        readline = stdin.readline
        s = readline().split()
        if int(s[0]) == 1:
            if reverse == 1:
                reverse = 0
            else:
                reverse = 1
        else:
            if int(s[1]) == 1:
                if reverse == 1:
                    tail.append(s[2])
                else:
                    head_deque.appendleft(s[2])
            else:
                if reverse == 1:
                    head_deque.appendleft(s[2])
                else:
                    tail.append(s[2])
    head = list(head_deque)
    head = ''.join(head)
    tail = ''.join(tail)
    if reverse == 1:
        print(tail[::-1]+S[::-1]+head[::-1])
    else:
        print(head+S+tail)
        
main()
### BUGGY CODE ###

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

m=10**9+7

dp=[ [0]*(k+1) for _  in range(n+1) ]
dp[0][0]=1

for i in range(n):
    for j in range(k+1):
        if j-a[i]>=0:
            dp[i+1][j]=sum( dp[i][j-a[i]:j+1 ])
        else:
            dp[i+1][j]=sum( dp[i][0:j+1 ])

print(dp[n][k]%m)

### FIXED CODE ###

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

m=10**9+7

dp=[ [0]*(k+1) for _  in range(n+1) ]
dp[0][0]=1

dp_sum=[ [0]*(k+1) for _  in range(n+1) ]

for i in range(n):
    for j in range(k+1):
        if j==0:
            dp_sum[i][j]=1
        else:
            dp_sum[i][j]= (dp_sum[i][j-1]+dp[i][j])%m
        if j-a[i]>0:
            dp[i+1][j]= (dp_sum[i][j] - dp_sum[i][j-a[i]-1])%m
        else:
            dp[i+1][j]= (dp_sum[i][j])%m

print(dp[n][k]%m)
### BUGGY CODE ###

from functools import lru_cache
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))
    

### FIXED CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))
### BUGGY CODE ###

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

list=list(S)

kei=[]
for a in range(N-2):
    for b in range(N-1):
        if b<=a:
            continue
        for c in range(N):
            if c<=b:
                continue
            retsu=''
            retsu=retsu+list[a]+list[b]+list[c]
            kei.append(retsu)
last=set(kei)
print(len(last))


### FIXED CODE ###

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

list=list(S)

count=0
for a in range(10):
    find1=S.find(str(a))
    if find1==-1:
        continue
    for b in range(10):
        find2=S[find1+1:].find(str(b))
        if find2==-1:
            continue
        for c in range(10):
            find3=S[find1+1+find2+1:].find(str(c))
            if find3==-1:
                continue
            count+=1
print(count)
### BUGGY CODE ###

s = input()
count = 0
while True:
    N = len(s)
    for n in range(N-1):
        if s[n] != s[n+1]:
            s = s[:n] + s[n+2:]
            count += 2
            break
    else:
        break
print(count)

### FIXED CODE ###

S = input()
a = []
for s in S:
    if not a:
        a.append(s)
        continue
    if s != a[-1]:
        a.pop()
    else:
        a.append(s)
print(len(S)-len(a))
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [collections.Counter(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
for i, s in enumerate(S) :
    for ss in range(i + 1, N) :
        if s == S[ss] :
            ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [''.join(sorted(input())) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
dic = {}
for s in S :
    if not s in dic :
        dic[s] = 0
    
    ans += dic[s]
    dic[s] += 1

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

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

ans = 0
num = 1000000007

for i in range(n-1):
    for j in range(i, n):
        ans += (a[i] ^ a[j])
        ans %= num

print(ans)

### FIXED CODE ###

import numpy as np

MOD = 10**9 + 7
n = int(input())
a = np.array(input().split(), np.int64)
max_num = np.max(a)
digit_num = len(format(max_num, 'b'))
ans = 0
for digit in range(digit_num):
    b = (a >> digit) & 1
    one = np.count_nonzero(b)
    zero = n - one
    ans += 2 ** digit * (one * zero)
    ans %= MOD

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

#C - Unification
S = list(input())

count = 0
i = 0
while len(set(S))>1:
    if S[i] != S[i+1]:
        S.pop(i)
        S.pop(i)
        count += 2
        if i != 0:
            i -= 1
    else:
        i += 1
print(count)

### FIXED CODE ###

S = list(input())
one = S.count('1')
zero = S.count('0')

print(2*min(one,zero))
### BUGGY CODE ###

def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, _x + _y + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

print(solve(_x, _y))


### FIXED CODE ###

def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    n = (x + y) // 3
    r = min((2 * y - x) // 3, (2 * x - y) // 3)
    return cmb(n, r, mod)

_x, _y = map(int, input().split())

mod = 10 ** 9 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range(2, max(_x, _y) + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((- inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

print(solve(_x, _y))
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
sum = 0
max = 0
index = 0
value = 0.000000000000

for i in range(n - k + 1):
    sum = 0
    for j in range(k):
        sum += p_list[i + j]
    if sum > max:
        max = sum
        index = i

for i in range(k):
    for j in range(p_list[index + i]):
        value += (j + 1) / p_list[index + i]

print(value)


### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
num = sum(p_list[0:k])
max = 0
index = 0
value = 0

for i in range(n - k):
    num = num + p_list[i + k] - p_list[i]
    if num > max:
        max = num
        index = i + 1

for i in range(k):
    value += (1 + p_list[index + i])/ 2

print(value)
### BUGGY CODE ###

x,k,d = map(int,input().split())
for i in range(k):
    if x >= 0:
        x -=d
    elif x < 0:
        x +=d
print(abs(x))


### FIXED CODE ###

#移動の最小値(高速化問題)
x,k,d = map(int,input().split())
x = abs(x)
if (x//d) > k:
    ans = x - d*k
elif (k-(x//d))%2 == 0:
    y = x-(x//d)*d
    ans = y
else:
    y = x-(x//d)*d
    ans = y-d
print(abs(ans))
### BUGGY CODE ###

n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]

egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()
ans = 0
INF = 10 ** 10
for d, u, v in egde:
    d2 = INF
    for w in range(n):
        if w == u or w == v:
            continue
        d2 = min(d2, adjacency_list[u][w] + adjacency_list[w][v])
    if d < d2:
        ans += d
    elif d > d2:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))
### BUGGY CODE ###

import bisect
N = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        work = l[:j]
        x = l[i] - l[j]
        idx = bisect.bisect_right(work, x)
        ans += len(work) - idx
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        #work = l[:j]
        x = l[i] - l[j]
        #idx = bisect.bisect_right(work, x)
        idx = bisect.bisect_right(l, x)
        ans += max(j - idx , 0)
print(ans)
### BUGGY CODE ###

s = list(input())
count = 0
while True:
    if len(s) <=1:
        break
    for i in range(0,len(s)-1):
        if s[i] != s[i+1]:
            count += 2
            del s[i]
            del s[i]
            break
    else:
        break
print(count)

### FIXED CODE ###

s = list(input())
zero = s.count("0")
ans = min(len(s)-zero,zero)
print(ans*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
nums = [0]*N
n = 0
routes = []
groups = dict()
for _ in range(M):
    A,B = map(int,input().split())
    routes.append((A-1,B-1))

for i in range(M):
    a = routes[i][0]
    b = routes[i][1]
    if nums[a] == 0 and nums[b] == 0:
        n += 1
        groups[n] = {a, b}
        nums[a] = n
        nums[b] = n
    elif nums[a] == 0 and nums[b] != 0:
        nb = nums[b]
        nums[a] = nb
        groups[nb].add(a)
    elif nums[a] != 0 and nums[b] == 0:
        na = nums[a]
        nums[b] = na
        groups[na].add(b)
    elif nums[a] != nums[b]:
        na = nums[a]
        nb = nums[b]
        for num in groups[nums[b]]:
            nums[num] = na
        groups[na] = groups[na] | groups[nb]
        del groups[nb]

ans = 0
for g in groups.values():
    l = len(g)
    if l > ans:
        ans = l
print(max(ans,1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
nums = [0] * N
friends = []
for _ in range(N):
    friends.append(set())

for _ in range(M):
    A, B = map(int, input().split())
    friends[A-1].add(B-1)
    friends[B-1].add(A-1)

gnum = 0
groupn = 0
nmax = 0

def find_route(i):
    global gnum
    global nums
    global friends
    global groupn
    global nmax
    if len(friends[i]) == 0:
        return
    if nums[i] == 0:
        gnum += 1
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

for i in range(N):
    find_route(i)

print(max(nmax, 1))
### BUGGY CODE ###

import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = float("inf")


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    global ans
    if tmp > ans:
        return
    if x == H - 1 and y == W - 1:
        if tmp == 0:
            print(0)
            exit()
        ans = tmp
        return ans
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():
    dp = [[0] * W for _ in range(H)]

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "#":
                    dp[0][0] = 1
            elif x == 0:
                if s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][x] == "#" and s[y][x - 1] == "." and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
                elif s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = min(dp[y][x - 1] + 1, dp[y - 1][x])
                elif s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x] + 1)
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])

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


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()
### BUGGY CODE ###

from bisect import *
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
data = []
for _ in range(M):
    B, C = map(int, input().split())
    data.append((B, C))
data.sort(key=lambda x:x[1], reverse=True)

D = []
for B, C in data:
    i = bisect_left(A, C)
    if B<=i:
        D += [C]*B
    else:
        D += [C]*i

res = 0
for i in range(N):
    if i>=len(D) or A[i] > D[i]:
        res += A[i]
    else:
        res += D[i]
print(res)

### FIXED CODE ###

from bisect import *
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
data = []
for _ in range(M):
    B, C = map(int, input().split())
    data.append((B, C))
data.sort(key=lambda x:x[1], reverse=True)

D = []
for B, C in data:
    i = bisect_left(A, C)
    p = min(B, i)
    if len(D)+p <N:
        D += [C]*p
    else:
        D += [C]*(N-len(D))
        break

res = 0
for i in range(N):
    if i>=len(D) or A[i] > D[i]:
        res += A[i]
    else:
        res += D[i]
print(res)
### BUGGY CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
print(int(ABC[N]%(10**9+7)))

### FIXED CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))
### BUGGY CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    a = [int(s) for s in input().split()]
    heapq.heapify(a)

    for _ in range(m):
        b, c = map(int, input().split())
        for _ in range(b):
            if a[0] >= c:
                break
            heapq.heapreplace(a, c)
    
    print(sum(a))

main()


### FIXED CODE ###

from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = [int(s) for s in input().split()]
    cnt = defaultdict(int)

    for x in a:
        cnt[x] += 1
    
    for _ in range(m):
        b, c = map(int, input().split())
        cnt[c] += b
    
    rest = n
    s = 0
    for k in sorted(cnt.keys(), reverse=True):
        if cnt[k] >= rest:
            s += k * rest
            rest = 0
            break
        else:
            s += k * cnt[k]
            rest -= cnt[k]
    
    print(s)

main()