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

#!/usr/bin/env python3


def solve(H, W, S):
    grid = [0] * (W * H)
    for y in range(H):
        count = 0
        start = 0
        for x in range(W):
            if S[y][x] == '#':
                for i in range(start, x):
                    grid[y*W+i] = count
                start = x + 1
                count = 0
            else:
                count += 1
        for i in range(start, W):
            grid[y*W+i] = count

    ans = 1
    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                for i in range(start, y):
                    if ans < grid[i*W+x] + count:
                        ans = grid[i*W+x] + count
                start = y + 1
                count = 0
            else:
                count += 1
        for i in range(start, H):
            if ans < grid[i*W+x] + count:
                ans = grid[i*W+x] + count

    return ans - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3


def solve(H, W, S):
    grid = [[0] * W for _ in range(H)]
    for y in range(H):
        count = 0
        start = 0
        for x in range(W):
            if S[y][x] == '#':
                for i in range(start, x):
                    grid[y][i] = count
                start = x + 1
                count = 0
            else:
                count += 1
        for i in range(start, W):
            grid[y][i] = count

    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                for i in range(start, y):
                    grid[i][x] += count
                start = y + 1
                count = 0
            else:
                count += 1
        for i in range(start, H):
            grid[i][x] += count

    ans = 0
    for x in range(W):
        for y in range(H):
            if grid[y][x] > ans:
                ans = grid[y][x]
    return ans - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

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

H, W, M = map(int,input().split())

X = [0] * H
Y = [0] * W
 
C = {}
for i in range(H):
    for j in range(W):
        C[(i, j)] = False
A = []
m = M
while m:
    m -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    C[(x, y)] = True
    X[x] += 1
    Y[y] += 1

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

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = False
for i in xms:
    for j in yms:
        if not C[(i, j)]: ans = True
        
cnt = xm + ym         
print(cnt if ans else cnt - 1)

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, W, M = map(int,input().split())
q=set(tuple(map(lambda x :int(x)-1,input().split())) for _ in range(M))

X = [0] * H
Y = [0] * W

for i, j in q:
    X[i] += 1
    Y[j] += 1
    
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = xm + ym - 1

bl = False
for i in xms:
    for j in yms:
        if not (i, j) in q:
            print(ans + 1)
            sys.exit()
            bl = True
            
print(ans)
### BUGGY CODE ###

from collections import defaultdict as d
p=d(str)
n=int(input())
print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    print(n-1,flush=True)
    t=input()
    if t == "Vacant": exit()
    else:
        p[0]=s
        p[n-1]=t
        l=0
        r=n-1
        while r-l>1:
            g=(l+r)//2
            if p[l]=="":
                print(l, flush = True)
                s = input()
                p[l]=s
                if s == "Vacant": exit()
                else:
                    s=p[l]
            if p[g]=="":
                print(g, flush = True)
                t = input()
                p[g]=t
                if t == "Vacant": exit()
                else:
                    t=p[g]
            if ((g-l)%2!=0 and s!=t) or ((g-l)%2!=1 and s==t):
                l=g
            else:
                r=g
        if p[l]=="":
            print(l, flush = True)
            s = input()
            if s == "Vacant": exit()
        if p[r]=="":
            print(r, flush = True)
            t = input()
            if t == "Vacant": exit()


### FIXED CODE ###

from collections import defaultdict as d
p=d(str)
n=int(input())
print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    p[0]=s
    p[n]=s
    l=0
    r=n
    while 1:
        g=(l+r)//2
        print(g, flush = True)
        s = input()
        p[g]=s
        if s == "Vacant": break
        else:
            t=p[l]
            if ((g-l)%2!=0 and s!=t) or ((g-l)%2!=1 and s==t):
                l=g
            else:
                r=g
### BUGGY CODE ###

inputS = input()
S = list(inputS)
count = 0
tmpI = 0
tmpJ = 0

for _ in range(inputS.count('W')):
  i = inputS.find('W',tmpI)
  tmpI = i + 1
  j = inputS.find('B',tmpJ)
  tmpJ = j + 1
  S = list(inputS)
  S[i] = 'B'
  inputS = ''.join(S)
  count += (i-j)    
print(count)

### FIXED CODE ###

S = list(input())
count = 0
valueA = 0
for i in range(len(S)):
  if S[i] == 'B':
    count += 1
    valueA += i

valueB = 0
for i in range(count):
  valueB += (len(S) - 1 - i)
  
print(valueB - valueA)
### BUGGY CODE ###

import bisect

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

arr.sort()

for _ in range(m):
    q = arr.pop()
    bisect.insort_right(arr, q // 2)

print(sum(arr))

### FIXED CODE ###

from heapq import heapify, heapreplace

n, m = map(int, input().split())
arr = [-x for x in map(int, input().split())]
heapify(arr)

for _ in range(m):
    heapreplace(arr, int(arr[0] / 2))

print(-sum(arr))
### BUGGY CODE ###

# coding: utf-8
N, M = map(int, input().split())
AB = []
d = {}
g = {}
for _ in range(N):
    a, b = list(map(int, input().split()))
    # AB.append(tmp[:])
    if a > M:
        continue
    if a not in d.keys():
        d[a] = [b]
        g[a] = [False]
    else:
        d[a].append(b)
        g[a].append(False)
day = 0
ans = 0
for i in range(M):
    good = -1
    flag = False
    for key in list(sorted(d.keys(), reverse=True)):
        if key + day > M:
            continue
        for j in range(len(d[key])):
            if good < d[key][j] and not g[key][j]:
                good = d[key][j]
                idx = key
                jdx = j
                flag = True
    if flag:
        g[idx][jdx] = True
        ans += good
    day += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
AB = []
heapify(AB)
d = {}
for _ in range(N):
    a, b = list(map(int, input().split()))
    if a > M:
        continue
    if a not in d.keys():
        d[a] = [-b]
    else:
        d[a].append(-b)
day = M - 1
ans = 0
ables = []
while day >= 0:
    now = M - day
    if now in d.keys():
        for v in d[now]:
            heappush(ables, v)
    if len(ables) > 0:
        v = heappop(ables)
        ans += -1 * v
    day -= 1
print(ans)
### BUGGY CODE ###

# dp[i][j] i番目までの品物で、重さがj以下になるよう選んだときの価値の最大値
# 0<=i<N+1, 0<=j<W+1  i=0, j=0のときはdpはすべて0
# 初期値 dp[1] j<w1ならdp[1][j]=0, j>=w1ならdp[1][j]=v1
# dp[i+1][j]の求め方 i+1番目の品物を選ぶかどうか
# j-w(i+1)<0のとき、dp[i+1][j] = dp[i][j]
# j-w(i+1)>=0のとき、dp[i+1][j]=max(dp[i][j], dp[i][j-w(i+1)]+v(i+1))
# 解答はdp[N][W]

# 入力
# tableは二次元配列　table[i][0]でi番目の品物の重さ、table[i][1]で価値 i=0は添え字をdpとそろえるためにつけた
N, W = list(map(int, input().strip().split()))
table = [[0, 0]]
for i in range(1, N+1):
    table.append(list(map(int, input().strip().split())))


# 初期化 dpテーブルの行数はN+1, 列数はW+1
dp = [[0] * (W + 1) for i in range(N + 2)]

# 初期値 i=1
for j in range(W + 1):
    if j < table[1][0]:
        dp[1][j] = 0
    else:
        dp[1][j] = table[1][1]

# dpテーブル
for i in range(1, N):
    for j in range(W + 1):
        if j - table[i+1][0] < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - table[i + 1][0]] + table[i + 1][1])

print(dp[N][W])

### FIXED CODE ###

# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 参考 https://qiita.com/drken/items/68b8503ad4ffb469624c

import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

# dpテーブル
for i in range(N):
    w, v = map(int, input().strip().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(dp[-1])
### BUGGY CODE ###

import itertools
N, M, K = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(N)]
min_cost = 10**9
for q in itertools.permutations(Q):
  cost = 0
  C = [0] * M
  for i in q:
    cost += i[0]
    for j,c in enumerate(i[1:]):
      C[j] += c
    if len([c for c in C if c >= K]) == M:
      min_cost = min([cost, min_cost])
      break
print(min_cost) if min_cost != 10**9 else print(-1)

### FIXED CODE ###

import numpy as np
import itertools
N, M, K = map(int, input().split())
Q = [np.asarray(input().split(), dtype=int) for i in range(N)]
min_cost = 10**9
def dfs(cost, C, depth=0):
  global min_cost
  if (C >= K).all():
    min_cost = min([cost, min_cost])
    return
  if depth == N:
    return
  dfs(cost+Q[depth][0], C + Q[depth][1:], depth+1)
  dfs(cost, C, depth+1)
  
dfs(0, np.zeros(M))
    
print(min_cost) if min_cost != 10**9 else print(-1)
### BUGGY CODE ###

import math

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

now_max = 1

for i in range(int(math.pow(P, 1 / N)) + 1, 0, -1):
    if P % (i ** N) == 0:
        now_max = i
        break

print(now_max)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

import numpy as np

def main():
    N = int(input())
    P = np.array([int(x) for x in input().split()])
    ans = 0

    for i in range(N):
        if P[i] <= min(P[0:i+1]):
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    ans = 0
    minP = P[0]

    for i in range(N):
        minP = min(minP, P[i])
        if P[i] <= minP:
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy
from collections import deque
import numpy as np

h, w = map(int, input().split())
s = np.array([list(map(str, input().rstrip())) for _ in range(h)])


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = np.full_like(s, 0).astype(int)
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and grid[cx + mx][cy + my] == 0:
                        if s[cx][cy] != s[cx + mx][cy + my]:
                            grid[cx + mx][cy + my] = grid[cx][cy] + 1
                            q.append((cx + mx, cy + my))
            grid = grid.flatten()
            grid[np.where(grid == 0)] = 1
            ans += (grid % 2 == 0).sum()
        else:
            continue

print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
B = [0]*N
for _ in range(K):
  for i in range(N):
    a = max(0,i-A[i])
    b = min(N-1,i+A[i])
    for j in range(a,b+1):
      B[j] += 1
  if A == B:
    break
  A=B
  B = [0]*N
print(*A)

### FIXED CODE ###

import sys
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)

@jit
def imos(A):
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    a = max(0,i-x)
    b = min(N-1,i+x)
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)
print(*A)
### BUGGY CODE ###

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

dic = {a+1:0 for a in range(10**5)}
for a in A:
  dic[a] += 1

for i in range(Q):
  B, C = list(map(int, input().split()))
  dic[C] += dic[B]
  dic[B] = 0
  
  ans = 0
  for k, v in dic.items():
    ans += k*v
  
  print(ans)


### FIXED CODE ###

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

ans = sum(A)
dic = {a+1:0 for a in range(10**5)}
for a in A:
  dic[a] += 1

for i in range(Q):
  B, C = list(map(int, input().split()))
  ans += dic[B]*(C-B)
  dic[C] += dic[B]
  dic[B] = 0
    
  print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [1]
i = 1
n = 0
l = 1
while 1:
  i = A[i]
  if i not in B:
    B.append(i)
    l = l + 1
    if l == K + 1:
      print(i)
      break
  else:
    n = B.index(i)
    print(B[n + (K-n) % (l-n)])
    break

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [-1 for i in range(N+1)]
B[1] = 0
n = 1
m = 0
while 1:
  n = A[n]
  m += 1
  if m == K:
    print(n)
    break
  if B[n] == -1:
    B[n] = m
  else:
    a = (K - m) % (m - B[n])
    for i in range(a):
      n = A[n]
    print(n)
    break
### BUGGY CODE ###

s = input()
q = int(input())
f = 1
for i in range(q):
  query = input()
  if query[0] == '1':
    f *= -1
  else:
    if f == 1:
      if query[2] == '1':
        s = query[4] + s
      else:
        s += query[4]
    else:
      if query[2] == '1':
        s += query[4]
      else:
        s = query[4] + s
if f == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
flag = 1
f = ''
b = ''
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    flag *= -1
  else:
    if flag == 1:
      if query[1] == '1':
        f += query[2]
      else:
        b += query[2]
    else:
      if query[1] == '1':
        b += query[2]
      else:
        f += query[2]
ans = f[::-1] + s + b
if flag == -1:
  ans = ans[::-1]
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
a = [K]*N
for i in range(Q):
  b = [1]*N
  s = int(input())
  b[s-1] = 0
  for j in range(N):
    a[j] -= b[j]

for i in a:
  if i > 0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

N, K, Q = map(int, input().split())
a = [-1*Q]*N
for i in range(Q):
  s = int(input())
  a[s-1] += 1

for i in a:
  #print(i)
  if K + i > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import bisect

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

num_b = [0 for _ in range(n)]
j = 0
for i in range(n):
    if j == n:
        num_b[i] = n
        continue
    while a[j] < b[i]:
        j += 1
        if j == n:
            break
    num_b[i] = j

ans = 0
j = 0
for i in range(n):
    while b[j] < c[i]:
        j += 1
        if j == n:
            ans += (n - i) * sum(num_b)
            break
    if j == n:
        break
    ans += sum(num_b[:j])

print(ans)


### FIXED CODE ###

import bisect

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

num_b = [0 for _ in range(n)]
j = 0
for i in range(n):
    if j == n:
        num_b[i] = n
        continue
    while a[j] < b[i]:
        j += 1
        if j == n:
            break
    num_b[i] = j

ans = 0
j = 0
temp_sum = 0
for i in range(n):
    while b[j] < c[i]:
        temp_sum += num_b[j]
        j += 1
        if j == n:
            ans += (n - i) * sum(num_b)
            break
    if j == n:
        break
    ans += temp_sum

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

a,b=map(int, input().split())

def calcCommonDivisor(a, b):
    cdiv=[]
    for i in range(1, max(a,b)+1):
        if a%i==0 and b%i==0:
            cdiv.append(i)

    return cdiv

def isPrime(a):
    if a == 1:
        return True

    d=[]
    for i in range(1, a+1):
        if a%i==0:
            d.append(i)

    return len(d) == 2

cdiv=calcCommonDivisor(a,b)
if len(cdiv) == 1:
    print(1)
    quit()

ans=0
for i in cdiv:
    if isPrime(i):
        ans+=1

print(ans)


### FIXED CODE ###

import fractions
a, b = map(int, input().split())

def factorize(n: int) -> int:
    b = 2
    ret = []
    while b*b <= n:
        while n%b == 0:
            n //= b
            ret.append(b)
        b = b + 1

    if n > 1:
        ret.append(n)

    return list(set(ret))

g = fractions.gcd(a, b)
print(len(factorize(g))+1)
### BUGGY CODE ###

from collections import deque

N,H=map(int,input().split())
a=deque([]);b=deque([])
for _ in range(N):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)
bb=deque([])
for i in range(N):
    if b[i]>=max(a):
        bb.append(b[i])
if sum(bb)>=H:
    print(len(bb))
else:
    ans=int((H-sum(bb))/max(a))+len(bb)
    if (H-sum(bb))%max(a)==0:
        print(ans)
    else:
        print(ans+1)

### FIXED CODE ###

N,H=map(int,input().split())
S=[[int(x) for x in input().split()] for _ in range(N)]
A,B=zip(*S)
A=max(A)
B=[b for b in B if b>A]
B.sort(reverse=True)
ans=0
cnt=0
for b in B:
    if H<=0:
        break
    cnt+=1
    H-=b
if H>0:
    cnt+=(H-1)//A+1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 10**9 + 7
num_a = [0]*60
str_a = []
for i in a:
  a_str = format(i, 'b').zfill(60)
  str_a.append(a_str)
  for j in range(len(a_str)):
    if a_str[-1-j] == '1':
      num_a[j] += 1
ans = 0
cnt = 0
for i in str_a:
  cnt += 1
  if cnt >= n:
    break
  for j in range(len(i)):
    if i[-1-j] == '1':
      num_a[j] -= 1
      ans += (n-cnt-num_a[j])*2**j
      ans = ans % p
    else:
      ans += num_a[j]*2**j % p
      ans = ans % p
      
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
p = 10**9 + 7
ans = 0
for i in range(60):
  c = np.count_nonzero(a & 1)
  ans = (ans + c*(n-c)*2**i) % p
  a = a >> 1
print(ans)
### BUGGY CODE ###

h,w,n=map(int,input().split())
jl=[0]*10
ab=[]
if n==0:
  print((w-2)*(h-2))
  for i in range(9):
    print(0)
  exit()
for i in range(n):
  a,b=map(int,input().split())
  a-=1
  b-=1
  for j in range(max(0,b-2),min(w-2,b+1)):
    for k in range(max(0,a-2),min(h-2,a+1)):
      ab=ab+[[k,j]]

ab.sort(key=lambda x: x[1])
ab.sort()
flag=False
count=1
now=ab[0]
for i in ab[1:]:
  if i==now:
    count+=1
  else:
    jl[count]+=1
    count=1
    now=i
jl[count]+=1
jl[0]=(h-2)*(w-2)-sum(jl[1:])
for i in range(10):
  print(jl[i])

### FIXED CODE ###

h,w,n=map(int,input().split())
jl=[0]*10
cnt={}
if n==0:
  print((w-2)*(h-2))
  for i in range(9):
    print(0)
  exit()
for i in range(n):
  a,b=map(int,input().split())
  a-=1
  b-=1
  for j in range(max(0,b-2),min(w-2,b+1)):
    for k in range(max(0,a-2),min(h-2,a+1)):
      if (k, j) in cnt:
        cnt[(k, j)]+=1
      else:
        cnt[(k, j)]=1
jl[0]=(h-2)*(w-2)
for i in cnt.values():
  jl[0]-=1
  jl[i]+=1
for i in jl:
  print(i)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    for _ in range(M):
        A.sort()
        A[N-1] = A[N-1] // 2
        if A[N-1] < A[N-2]:
            A[N-1], A[N-2] = A[N-2], A[N-1]
    
    return sum(A)

print(solve())

### FIXED CODE ###

import heapq

def solve():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) * -1, input().split()))
    
    heapq.heapify(A)
    
    for _ in range(M):
      t = heapq.heappop(A)
      heapq.heappush(A, -1*(-t//2))
    
    return -sum(A)

print(solve())
### BUGGY CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B, C = zip(*[list(map(int, input().split())) for _ in range(M)])

A.sort()
lo = 0
for b, c in zip(B, C):
    ci = bisect.bisect_left(A, c, lo)
    A[ci:ci] = [c] * b
    lo += b

print(sum(A[-N:]))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = [list(map(int, reversed(input().split()))) for _ in range(M)]

A.sort()
CB.sort()

ans = 0
for _ in range(N):
    a = A[-1] if A else -INF
    c, b = CB[-1] if CB else (-INF, -INF)
    if a > c:
        ans += a
        A.pop()
    else:
        ans += c
        CB[-1][1] -= 1
        if CB[-1][1] <= 0:
            CB.pop()
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
inp=list(map(len,input().split("T")))
inx,iny=list(map(int,input().split()))
memo={}
def tg(g,n,t):
 if (tuple(g),n,t) in memo:
  return memo[(tuple(g),n,t)]
 if g==[]:
  if n==t:
   return True
  else:
   return False
 if tg(g[1:],n+g[0],t)or tg(g[1:],n-g[0],t):
  memo[(tuple(g),n,t)]=True
  return True
 else:
  memo[(tuple(g),n,t)]=False
  return False

if tg(inp[1::2],0,iny)and tg(inp[2::2],inp[0],inx):
 print("Yes")
else:
 print("No")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
inp=list(map(len,input().split("T")))
inx,iny=list(map(int,input().split()))
memo={}
def tg(g,n,t):
 g.sort()
 g.reverse()
 def tn(g,n,t):
  if (tuple(g),n,t) in memo:
   return memo[(tuple(g),n,t)]
  if g==[]:
   if n==t:
    return True
   else:
    return False
  if n<t:
   z=tn(g[1:],n+g[0],t)
   memo[(tuple(g),n,t)]=z
   return z
  else:
   z=tn(g[1:],n-g[0],t)
   memo[(tuple(g),n,t)]=z
   return z
 return tn(g,n,t)
 
if tg(inp[1::2],0,iny)and tg(inp[2::2],inp[0],inx):
 print("Yes")
else:
 print("No")
### BUGGY CODE ###

S = input()

ans = 0
while S.count("01") or S.count("10"):
  if S.count("01"):
    ans += S.count("01")
    S = S.replace("01", "")
  if S.count("10"):
    ans += S.count("10")
    S = S.replace("10", "")
    
print(ans*2)    

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
stack = []
count = 0
for s in S:
  if not stack:
    stack.append(s)
  elif s != stack[-1]:
    stack.pop()
    count += 2
  else:
    stack.append(s)
print(count)
### BUGGY CODE ###

N = int(input())
m = 0
for i in range(1, N):
    m += i % (i+1)
print(m)

### FIXED CODE ###

N = int(input())
ans = ((N - 1) * N ) // 2
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D.keys():
  for j in E.keys():
    if i==j:
      ans+=D[i]*E[i]
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D:
  if i in E:
    ans+=D[i]*E[i]
print(ans)