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

MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
l, r = 1, 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = 0 if LR[i-1] == 1 else 1
    else:
        LR[i] = LR[i-1]
    if LR[i] == 0:
        l += 1
    else:
        r += 1
if l != r:
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)

### FIXED CODE ###

MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
l, r = 1, 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = 0 if LR[i-1] == 1 else 1
    else:
        LR[i] = LR[i-1]
    if LR[i] == 0:
        l += 1
    else:
        r += 1
if l != r:
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        count %= MOD
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    food=[]
    for _ in range(n):
        a,b=map(int, input().split())
        food.append([a,b])
    food.sort(key=lambda x:x[0]*-1)
    for j in range(n):
        a,b=food[j][0],food[j][1]
        dptmp=[0]*t
        for i in range(t):
            if i < a: 
                dptmp[i]=max(b,dp[i])
            else:
                dptmp[i]=max(dp[i-a]+b,dp[i])
        dp=dptmp
    print(dp[t-1])
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    food=[]
    for _ in range(n):
        a,b=map(int, input().split())
        food.append([a,b])
    food.sort(key=lambda x:x[0]*-1)
    for j in range(n):
        a,b=food[j][0],food[j][1]
        dptmp=[0]*t
        for i in range(t):
            if i < a: 
                dptmp[i]=max(b,dp[i])
            else:
                dptmp[i]=max(dp[i-a]+b,dp[i])
        dp=dptmp
    print(dp[t-1])
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
L = list(map(int, inputs[1].split()))

sort_L = sorted(L)
ans = 0
for i in range(n-2):
    a = sort_L[i]
    for j in range(i+1, n-1):
        b = sort_L[j]
        d = a+b
        for k in range(j+1, n):
            c = sort_L[k]
            if c < d:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
L = list(map(int, inputs[1].split()))
A = sorted(L)
 
ans = 0
for i in range(n-1, 0, -1):
    l, r = 0, i-1
    while l < r:
        if A[i] < A[l] + A[r]:
            ans += r-l
            r -= 1
        else:
            l += 1

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

n,m = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab = sorted(ab, key=lambda x:x[1], reverse = True)
income = 0
day = 1 #残り日数
i = 0

while day <= m:
  if ab[i][0] <= day:
    income += ab[i][1]
    ab.pop(i)
    day += 1
    i = 0
  else:
    i += 1
  if i >= len(ab):
    day += 1
    i = 0
  #print(day,i,income)
  
print(income)

### FIXED CODE ###

from heapq import heappop, heappush 
N, M = map(int, input().split())
score = 0
AB = [[] for i in range(M)]
for i in range(N):
  a, b = map(int, input().split())
  if M - a >= 0:
    AB[M - a].append(b)
  
#print(AB)
queue = []
for i in range(1, M + 1):
  for j in AB[-i]:
    heappush(queue, -j)
  if queue != []:
    score += -1 * heappop(queue)
  
  #print(score, queue)  
print(score)
### BUGGY CODE ###

n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print dp[-1]

### FIXED CODE ###

n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print(dp[-1])
### BUGGY CODE ###

# 数列aの最小値min_aの最大値はM//N
# 他の要素がmin_aの倍数であれば、min_aが最大公約数となる
# すなわち、(M-min_a)をmin_aで割った余りが0

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

for i in range(M//N, 0, -1):
    if (M - i)%i == 0:
        break
print(i)

### FIXED CODE ###

# 数列aの最小値min_aの最大値はM//N
# 他の要素がmin_aの倍数であれば、min_aが最大公約数となる
# すなわち、(M-min_a)をmin_aで割った余りが0

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

if M%2 == 0:
    for i in range(M//N, 0, -1):
        if (M - i)%i == 0:
            break
    print(i)    
else:
    if M//N % 2 == 0:
        min_a = M//N - 1
    else:
        min_a = M//N
    for i in range(min_a, 0, -2):
        if (M - i)%i == 0:
            break
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N = int(input())
    V = N
    dp = []
    for i in range(N):
        dp.append(list(map(int,input().split())))
    edge = [[True]*N for _ in range(N)]
    for k in range(V):
        for i in range(V):
            for j in range(V):
                a = dp[i][j]
                b = dp[i][k]+dp[k][j]
                if a > b:
                    print(-1)
                    exit(0)
                elif a == b and k != i and k != j:
                    edge[i][j] = False
                    edge[j][i] = False
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if edge[i][j]:
                ans += dp[i][j]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N = int(input())
    V = N
    dp = []
    for i in range(N):
        dp.append(list(map(int,input().split())))
    edge = [[True]*N for _ in range(N)]
    for k in range(V):
        for i in range(V):
            for j in range(V):
                a = dp[i][j]
                b = dp[i][k]+dp[k][j]
                if a > b:
                    print(-1)
                    exit(0)
                elif a == b and k != i and k != j:
                    edge[i][j] = False
                    edge[j][i] = False
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if edge[i][j]:
                ans += dp[i][j]
    print(ans)
### BUGGY CODE ###

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

res = 1
for e in A:
  res = res * e

if res > 10**18:
  print(-1)
else:
  print(res)

### FIXED CODE ###

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

if 0 in A:
  print(0)
  exit()

res = 1
for e in A:
  res = res * e
  if res > 10**18:
    print(-1)
    exit()

print(res)
### BUGGY CODE ###

import copy
n=int(input())
m=0
x=list(map(int,input().split()))
for i in range(n):
    y=copy.deepcopy(x)
    y.pop(i)
    if n%2==0:
        m=n//2
        y.sort()
        print(y[m-1])
    else:
        m=n//2
        y.sort()
        print((y[m]-y[m-1])/2)

### FIXED CODE ###

N = int(input())
arr = []
for x in list(map(int,input().split())):
    arr.append(x)
sort_arr = sorted(arr)
mid1 = sort_arr[N//2-1]
mid2 = sort_arr[N//2]

for x in arr:
    if x <= mid1:
        print(mid2)
    else:
        print(mid1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()

for i in range(len(S)-2):
    for j in range(i+1, len(S)-1):
        se = set(S[j+1:])
        for x in se:
            answer.add((S[i], S[j], x))
        #print(i, j, len(answer))

print(len(answer))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()
se1 = set()
for i in range(len(S)-2):
    x = S[i]
    if x in se1:
        continue
    se1.add(x)
    se2 = set()
    for j in range(i+1, len(S)-1):
        y = S[j]
        if y in se2:
            continue
        se2.add(y)
        se = set(S[j+1:])
        for z in se:
            answer.add((x, y, z))

print(len(answer))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,*a=map(int,open(0).read().split())
a.sort()
b=a[-1]
if n>10:
    a=a[n//3:n*2//3]
c=[cmb(b,i) for i in a]
print(b,a[c.index(max(c))])

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
b=a.pop()
dif=float("inf")
ans=0
for i in range(n-1):
    if abs(a[i]-b/2)<dif:
        ans=a[i]
        dif=abs(a[i]-b/2)
print(b,ans)
### BUGGY CODE ###


from collections import deque


def main():
        
    N = int(input())
    es = [[] for _ in range(N)]

    for i in range(N):
        s = input()
        for j in range(N):
            if i == j:
                continue
            if s[j] == "1":
                es[i-1].append(j-1)
                es[j-1].append(i-1)


    """
    あるノードを始点として、幅優先的に色塗りをしていく。
    これを、全ノードを始点にして試す
    """
    ans = -1
    for i in range(N):
        color = [0] * N
        
        q = deque()
        q.append((i, 1))
        tmp = 1
        flag = True
        while q and flag:
            node, c = q.popleft()
            color[node] = c
            
            for nxt in es[node]:
                if color[nxt] != 0:
                    if abs(color[node] - color[nxt]) != 1:
                        flag = False
                        break
                else:
                    q.append((nxt, c+1))
                    tmp = max(c+1, tmp)


        if flag:
            ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

"""
AtCoder Grand Contest 039  B - Graph Partition / 


（１）ある集合V_iに含まれるノードから伸びる辺について、その先の集合がV_i-1かV_i+1になるように分ける
（２）その時の集合の個数の最大値を求める

（１）を言い換えると、あるノードが偶数番の集合に属しているとき、それと繋がっているノードが奇数番号の集合かつ差が１である
　→二部グラフ
（２）V_1とV_kがあるとき、少なくともそれらはk本の辺をたどらなければ繋がれないはずなので、最も距離の長い辺（直径）を探す
"""

from collections import deque

N = int(input())
es = [[] for _ in range(N)]

for i in range(N):
    S = input()
    for j in range(N):
        if S[j] == "1":
            es[i].append(j)


q = deque()
q.append(0)
checked = [0] * N
checked[0] = 1
while q:
    curr = q.popleft()
    for nxt in es[curr]:
        # 未探索なので、currと別の集合に設定
        if checked[nxt] == 0:
            checked[nxt] = checked[curr] * -1
            q.append(nxt)
        else:
            # 探索済みなので、別の集合に属しているか確認し、同じであれば条件を満たさない
            if checked[nxt] == checked[curr]:
                print(-1)
                exit()



# グラフの直径を求める。それぞれのノードをスタート地点として、全ノード間の距離を求めたときの最大距離が直径
ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    # 距離＋１が答えなので、起点を１としておく
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)

    ans = max(ans, max(dist))

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

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  #print(ans)
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  return ans
"""
"""
ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)
"""
print(F(4,3))
"""


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
INF = 10**11+1
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print(max(dp[-1]))

### FIXED CODE ###

N, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print(max(dp[-1]))
### BUGGY CODE ###

a=int(input())
b=[int(input()) for i in range(a)] 
for  i in range(0,a,1):
    c=b.copy()
    c[i]=0
    print (max(c))

### FIXED CODE ###

a=int(input())
b=[int(input()) for i in range(a)]
m=max(b) 

if b.count(m)>=2:
    for i in range(a):
        print (m)
else:
    c=b.copy()
    c.sort(reverse=True)
    m2=c[1]
    for i in range(a):
        if b[i]==m:
            print(m2)
        else:
            print (m)
### BUGGY CODE ###

import sys
import numpy as np


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = np.array(sorted([int(n) for n in input().split()], reverse=True))[:, np.newaxis]
    vb = np.array(sorted([int(n) for n in input().split()], reverse=True))[np.newaxis, :]
    xy = min(x*y, k)
    vac = np.array(sorted((va + vb).reshape(-1), reverse=True)[:xy]).reshape(xy, 1)
    vc = np.array(sorted([int(n) for n in input().split()], reverse=True))[np.newaxis, :]
    xyz = min(x*y*z, k)
    print(*(sorted((vac + vc).reshape(-1), reverse=True)[:xyz]), sep="\n")


main()


### FIXED CODE ###

import sys


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = sorted([int(n) for n in input().split()], reverse=True)
    vb = sorted([int(n) for n in input().split()], reverse=True)
    xy = min(x*y, k)
    vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
    vc = sorted([int(n) for n in input().split()], reverse=True)
    xyz = min(x*y*z, k)
    print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")


main()
### BUGGY CODE ###

a,b,x=map(int,input().split())
count=0
for i in range(a,b+1):
    if i%x==0:
        count+=1
print(count)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[[A[-1]]]
nowN=max(A)+1
i=len(A)-2
while i>=0:
    #print(lst)
    lst2=[n[-1] for n in lst]
    if max(lst2)>A[i]:
        maxvalue=0
        maxvaluei=100000
        for n in range(len(lst2)):
            if lst2[n]>A[i] and lst2[n]>maxvalue:
                maxvalue=lst2[n]
                maxvaluei=n
        lst[maxvaluei].append(A[i])
                #break
    else:
        lst.append([A[i]])

    i-=1
print(len(lst))


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

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

n = int(input())

for b in range(1,n+1):
    count = 0
    for x in range(1,n-1):
        for y in range(x,n-1):
            for z in range(y,n-1):
                a = x**2+y**2+z**2+x*y+y*z+z*x
                if a == b:
                    if x == y and y ==z:
                        count+=1
                    else:
                        count+=3

    print(count)

### FIXED CODE ###


import math
n = int(input())

sqn = int(math.sqrt(n))+1
count = 0
aset = [0]*(n+1)
for x in range(1,sqn):
    for y in range(x,sqn):
        for z in range(y,sqn):
            a = x**2+y**2+z**2+x*y+y*z+z*x
            if a <= n:
                if x == y and y ==z:
                    aset[a] +=1
                else:
                    if x == y or y ==z:
                        aset[a] +=3
                    else:
                        aset[a] +=6

for i in range(1,n+1):
    print(aset[i])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for k in range(N):
    P[k] = (P[k] + 1 ) / 2
print(max([sum(P[n:n + K]) for n in range(N - K + 1)]))

### FIXED CODE ###

def INT():
    return int(input())

def LI():
    return list(map(int, input().split()))

def MI():
    return map(int, input().split())

N, K = MI()
p = LI()

def E(x):
    return (x + 1) / 2

for i in range(N):
    p[i] = E(p[i])
    
ans = sum(p[:K])
E_K = ans

for i in range(N - K):
    E_K += p[i + K] - p[i]
    ans = max(ans, E_K)

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

n=int(input())
i=0
j=n-1
a=input(i)
b=input(j)
print('hoge')

### FIXED CODE ###

n=int(input())
i=0
j=n-1
print(i)
a=input()
print(j)
b=input()
while 1:
    if j-i<2:
        print(i)
        _=input()
        print(j)
        if input()!='Vacant':
            print('助けてくれ～～～')
    k=(j-i)//2+i
    print(k)
    c=input()
    if(k-i)%2and a==c or not(k-i)%2and a!=c:
        j=k
    else:
        a=c
        i=k
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int, input().split())) for _ in range(Q)]

    dist = [[INF] * N for _ in range(N)]
    fuel = [[INF] * N for _ in range(N)]

    for i in range(N):
        dist[i][i] = 0
        fuel[i][i] = 0

    for fr, to, cost in ABC:
        if cost > L:
            continue
        fr -= 1
        to -= 1
        dist[fr][to] = cost
        dist[to][fr] = cost

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = dist[i][k] + dist[k][j]
                dist[i][j] = min(dist[i][j], d)
                if d <= L:
                    fuel[i][j] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

    ans = []
    for start, end in ST:
        start -= 1
        end -= 1
        ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

    print(*ans, sep='\n')


sol()



### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

import heapq
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapq.heapify(A)
    choice = [list(map(int, input().split())) for i in range(M)]

    for c in choice:
        for i in range(c[0]):
            pop = heapq.heappop(A)
            if pop < c[1]:
                heapq.heappush(A, c[1])
            else:
                heapq.heappush(A, pop)
                break
    
    print(sum(A))

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

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

from math import factorial
S = input()
cum = []
for i in range(len(S)-1, -1, -1):
    slice = S[i:len(S)]
    slice_n = int(slice)
    cum.append(slice_n % 2019)
cum = sorted(cum)
prev = cum[0]
ans = 0
cnt = 0
for c in cum:
    if c != prev:
        if prev == 0:
            ans += cnt
        ans += cnt * (cnt-1) // 2
        cnt = 1
    else:
        cnt += 1
    prev = c

if cnt > 1:
    if prev == 0:
        ans += cnt
    ans += cnt * (cnt-1) // 2
    cnt = 1

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

N = int(input())
s = [input() for i in range(N)]

n = N
max_num = 0
t = []
while n >= max_num:
    word = s[0]
    count = s.count(s[0])

    if count > max_num:
        max_num = count
        t = [s[0]]
    elif count == max_num:
        t.append(s[0])

    for i in range(count):
        s.remove(word)
    n = len(s)

t = sorted(t)
for i in t:
  print(i)


### FIXED CODE ###

import collections

N = int(input())
s = [input() for i in range(N)]

c = collections.Counter(s)
max_num = max(c.values())
d = []
for key,value in c.items():
  if value == max_num:
    d.append(key)

for i in sorted(d):
  print(i)