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

def main():
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    s = [input().rstrip() for _ in range(H)]

    def wallen(g):
        L = len(g[0])
        ret = []
        ret.append('#' * (L + 2))
        for row in g:
            t = '#' + row + '#'
            ret.append(t)
        ret.append('#' * (L + 2))
        return ret

    g = wallen(s)
    # print(*g, sep='\n')

    left = [[-1] * (W + 2) for _ in range(H + 2)]  # 各方向に移動したときにぶつかる障害物の位置
    right = [[-1] * (W + 2) for _ in range(H + 2)]
    up = [[-1] * (W + 2) for _ in range(H + 2)]
    down = [[-1] * (W + 2) for _ in range(H + 2)]

    for r in range(H + 2):
        for c in range(W + 2):
            if g[r][c] == '#':
                left[r][c] = c
            else:
                left[r][c] = left[r][c - 1]

        for c in reversed(range(W + 2)):
            if g[r][c] == '#':
                right[r][c] = c
            else:
                right[r][c] = right[r][c + 1]

    for c in range(W + 2):
        for r in range(H + 2):
            if g[r][c] == '#':
                up[r][c] = r
            else:
                up[r][c] = up[r - 1][c]

        for r in reversed(range(H + 2)):
            if g[r][c] == '#':
                down[r][c] = r
            else:
                down[r][c] = down[r + 1][c]

    ans = 0
    for r in range(H + 2):
        for c in range(1, W + 1):
            t = right[r][c] - left[r][c] + down[r][c] - up[r][c] - 3
            ans = max(ans, t)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = []
    x = 0
    for c in range(W):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(W - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = []
    x = 0
    for r in range(H):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(H - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = row_blocks[r][c] + col_blocks[c][r] - 1
        ans = max(ans, t)
print(ans)
### BUGGY CODE ###

k,n=map(int,input().split())
l1=list(map(int,input().split()))
l2 = [x+k for x in l1]
l=l1+l2
ans=[]
for i in range(n):
    tmpList=[]
    for j in range(n-1):
      tmpList.append(l[j+1+i]-l[i])
    ans.append(max(tmpList))
print (min(ans))

### FIXED CODE ###

k,n,*a=map(int,open(0).read().split())
a+=[k+a[0]]
print(k-max(y-x for x,y in zip(a,a[1:])))
### BUGGY CODE ###

N = int(input())
S =list(input())
count = float("INF")

for i in range(N):
    count = min(S[0:i].count('W') + S[i+1:N].count('E'), count)
print(count)

### FIXED CODE ###

N = int(input())
S =list(input())
ans = N
W = 0
E = S.count('E')

for i in range(N):
    if S[i] =='E':
        E -= 1
    ans = min(ans, W+E)
    if S[i] == 'W':
        W += 1
print(ans)
### BUGGY CODE ###

A,B,C=map(int,input().split())
ans="NO"
for i in range(1,10**10):
    if i%A==0:
        if i%B==C:
            ans='YES'
            break
    else:
        continue
print(ans)

### FIXED CODE ###

A,B,C=map(int,input().split())
ans="NO"
for i in range(A):
    if (B*i+C)%A==0:
        ans='YES'
print(ans)
### BUGGY CODE ###

 
n=int(input())
s=input()
#n=39
#s="RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

r=[]
g=[]
b=[]

for i in range(n):
    if s[i]=="R":
        r.append(i+1)
    elif s[i]=="G":
        g.append(i+1)
    else:
        b.append(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in range(len(r)):
    for ig in range(len(g)):
        imin=max(r[ir],g[ig])
        if abs(r[ir]-g[ig])+imin in b: 
            isum=isum+1
for ir in range(len(r)):
    for ib in range(len(b)):
        imin=max(r[ir],b[ib])
        if abs(r[ir]-b[ib])+imin in g: 
            isum=isum+1
for ig in range(len(g)):
    for ib in range(len(b)):
        imin=max(g[ig],b[ib])
        if abs(g[ig]-b[ib])+imin in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)

### FIXED CODE ###

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

r=set()
g=set()
b=set()

for i in range(n):
    if s[i]=="R":
        r.add(i+1)
    elif s[i]=="G":
        g.add(i+1)
    else:
        b.add(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in r:
    for ig in g:
        if (ir+ig)/2 in b: 
            isum=isum+1
for ir in r:
    for ib in b:
        if (ir+ib)/2  in g: 
            isum=isum+1
for ig in g:
    for ib in b:
        if (ig+ib)/2  in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)
### BUGGY CODE ###

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

N=int(input())
L=[[]]

for i in range(N):
    a=deque(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        #print(L[j],j)
        if len(L[j])==0 or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            del L[j][0]
            del L[X][0]
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

### FIXED CODE ###

N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)
### BUGGY CODE ###

# coding: utf-8

list = [int(i) for i in input().rstrip().split(" ")]

matsu_count = list[0]
require = sorted(list[1:])

matsu_list = sorted([int(input().rstrip()) for i in range(matsu_count)])

def get_mp(matsu:list):
    ans = 0
    for i in range(3):
        ans += abs(matsu[i] - require[i])
    return ans

def get_ans(matsu:list):
    if len(matsu) == 3:
        return get_mp(matsu)
    ans = 80000
    for i in range(len(matsu) - 3 + 1):
        ans = min(ans, get_mp(matsu[i:]))
    for i in range(len(matsu)):
        for j in range(i + 1, len(matsu)):
            sub_matsu = []
            for k in range(len(matsu)):
                if k == i or k == j:
                    continue
                else:
                    sub_matsu.append(matsu[k])
            sub_matsu.append(matsu[i] + matsu[j])
            ans = min(ans, get_ans(sorted(sub_matsu)) + 10)


    return ans

ans = get_ans(matsu_list)
print(ans)



### FIXED CODE ###

# coding: utf-8

list = [int(i) for i in input().rstrip().split(" ")]

matsu_count = list[0]
require = sorted(list[1:])

matsu_list = sorted([int(input().rstrip()) for i in range(matsu_count)])

def get_mp(matsu:list):
    ans = 0
    for i in range(3):
        ans += abs(matsu[i] - require[i])
    return ans
mp = {}

def get_ans(matsu:list):
    if len(matsu) == 3:
        return get_mp(matsu)
    key = "#".join(map(str, matsu))
    if key in mp:
        return mp[key]
    ans = 80000
    for i in range(len(matsu) - 3 + 1):
        for j in range(i + 1, len(matsu) - 2 + 1):
            for k in range(j + 1, len(matsu) - 1 + 1):
                ans = min(ans, get_mp([matsu[i],matsu[j], matsu[k]]))
    if ans > 0:
        for i in range(len(matsu)):
            for j in range(i + 1, len(matsu)):
                sub_matsu = []
                for k in range(len(matsu)):
                    if k == i or k == j:
                        continue
                    else:
                        sub_matsu.append(matsu[k])
                sub_matsu.append(matsu[i] + matsu[j])
                ans = min(ans, get_ans(sorted(sub_matsu)) + 10)

    mp[key] = ans
    return ans

ans = get_ans(matsu_list)
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)
ans = sum(sum_p[0:k])
for i in range(n - k + 1):
    if ans < sum(sum_p[i:i + k]):
        ans = sum(sum_p[i:i + k])
print(ans)


### FIXED CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)

ans = sum(sum_p[0:k])
check = sum(sum_p[0:k])
p = 0
for i in range(k,n):
    check = check + sum_p[i] - sum_p[i - k]
    if check > ans:
        ans = check
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
maxi = max(a)
for i in range(n):
  if a[i] == maxi:
    b = []
    b += a
    b.remove(maxi)
    print(max(b))
  else:
    print(maxi)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
b = []
b += a
b.sort()
if b[-1] == b[-2]:
  maxi = max(a)
  for i in range(n):
    print(maxi)
else:
  maxi = max(a)
  for i in range(n):
    if a[i] != maxi:
      print(maxi)
    else:
      print(b[-2])
### BUGGY CODE ###

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

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

for i in range(m):
    l,r=map(int,input().split())
    mylist[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        mylist[i][j]+=mylist[i][j-1]

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(P,Q+1):
        tmp+=mylist[j][Q]
    memo[P][Q]=tmp
    print(tmp)

### FIXED CODE ###

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

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

for i in range(m):
    l,r=map(int,input().split())
    mylist[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        mylist[i][j]+=mylist[i][j-1]

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(Q,P-1,-1):
        tmp+=mylist[j][Q]
        memo[j][Q]=tmp
    print(tmp)
### BUGGY CODE ###

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    h,n=map(int,input().split()) #n yen, m types
    ab=[list(map(int,input().split())) for i in range(n)]

    dp=[INFI for i in range(h+1)]
    dp[0]=0


    def f(h):

        for a,b in ab:
            for j in range(h+1):
                if j-a<0:
                    dp[j] = min(dp[j],b)
                else:
                    dp[j]=min(dp[j],dp[j-a]+b)
        return dp[h]

    print(f(h))


if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
 
import itertools
 
#import bisect
 
import copy
 
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
 
 
 
def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)
 
    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])
 
    print(dp[h])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 11)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][0] == dp[u][i][0]:
            dp[u][tail] = dp[u][i]
        elif dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

from collections import deque
a = input()
k_a = deque(a + 'K')
k_a.popleft()
a = deque(a)
ans = 'K'

while len(a) >0:
    l = a.popleft()
    k_l = k_a.popleft()
    if l == '?':
        if ans[-1] == 'P' or k_l == 'P':
            ans += 'D'
        elif k_l == 'D' or k_l == '?':
            ans += 'P'
        else:
            ans+='D'    
    else:
        ans += l
print(ans[1:])


### FIXED CODE ###

a = input()

print(a.replace('P?', 'PD').replace('?D', 'PD').replace('??', 'PD').replace('?', 'D'))
### BUGGY CODE ###

h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = [[1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [i]
        cnt = 0
        for k in range(i + 1, h):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(i - 1, -1, -1):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[l][j] += cnt
            check[l][j] = True

check = [[False for _ in range(w)] for _ in range(h)]
max_ans = 0
for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [j]
        cnt = 0
        for k in range(j + 1, w):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(j - 1, -1, -1):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[i][l] += cnt
            check[i][l] = True
            max_ans = max(max_ans, ans[i][l])
print(max_ans)

### FIXED CODE ###

h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = [[1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [i]
        cnt = 0
        for k in range(i + 1, h):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(i - 1, -1, -1):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[l][j] += cnt
            check[l][j] = True

check = [[False for _ in range(w)] for _ in range(h)]
max_ans = 0
for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [j]
        cnt = 0
        for k in range(j + 1, w):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(j - 1, -1, -1):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[i][l] += cnt
            check[i][l] = True
            max_ans = max(max_ans, ans[i][l])
print(max_ans)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
A=[0]*N
B=[0]*N
j=0
for i in [0]*N:
 h=input()
 if h in A:
  B[A.index(h)]+=1
 else:
  A[j]=h
  B[j]=1
  j+=1
d=max(B)
C=[]
for i in range(N):
 if B[i]==d:
  C.append(A[i])
C.sort()
for i in range(len(C)):
 print(C[i],end='')

### FIXED CODE ###

N=int(input())
dic={}
for i in range(N):
 a=input()
 if a in dic:
  dic[a]+=1
 else:
  dic[a]=1
c=max(dic.values())
keys = [k for k, v in dic.items() if v == c]
keys.sort()
for j in range(len(keys)):
 print(keys[j])
### BUGGY CODE ###

import numpy as np

n = int(input())
li = np.zeros(10**6)
a = np.array(list(map(int, input().split())))
a.sort()

u, counts = np.unique(a,return_counts=True)

for item in a:
  li[item-1] = 1
#print(li[:100])

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1

#print(li[:100])

for i in range(len(u)):
  if counts[i] >=2:
    li[u[i]-1] = 0

print(int(li.sum()))



### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a.sort()
li = np.zeros(a[-1])

u, counts = np.unique(a,return_counts=True)

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1

#print(li[:100])

for i in range(len(u)):
  if counts[i] >=2:
    li[u[i]-1] = 0

print(int(li.sum()))
### BUGGY CODE ###

import sys
fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
BC = sorted(BC, key=lambda x: x[1], reverse=True)


def f(a, n, v):
    count = 0
    for i in range(min(n, len(a))):
        if a[i] < v:
            count += 1
        else:
            break
    return v * count, a[count:]


sum__ = 0
for num, val in BC:
    sum_, As = f(As, num, val)
    sum__ += sum_

print(sum__ + sum(As))

### FIXED CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
now = 0
for val, num in BC_:
    if now >= len(As) or As[now] >= val:
        break

    if As[min(num - 1 + now, len(As) - 1)] < val:
        sum_ = val * min(num, len(As) - now)
        now += min(num, len(As) - now)
    else:
        count = 0
        for i in range(min(num, len(As)-now)):
            if As[i + now] < val:
                count += 1
            else:
                break
        sum_ = val * count
        now += count
    sum__ += sum_

print(sum__ + sum(As[now:]))