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

#!/usr/bin/env python3
import sys
import math
import collections
INF = float("inf")


def factorial(n):
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(N: int, M: int):
    ans = 0
    for i in range(1, int(M/N)+1):
        if M % i == 0:
            ans = i
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math


def GCD(a, b):
    # a < b
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def solve(N: int, M: int):
    # O(sqrt(M))
    yakusu = [i for i in range(1, int(math.sqrt(M))+1) if M % i == 0]
    yakusu.extend([M/y for y in yakusu[::-1]])

    ans = 0
    for y in yakusu:
        rest = M / y
        if rest >= N:
            # print(y, rest, N)
            ans = y

    print(int(ans))
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)


if __name__ == '__main__':
    main()
### 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 ###

n = int(input())
count = 0
while n > 1:
    for z in range(2, n+1):
        if n % z == 0:
            n = n / z
            count += 1
    break

print(count)

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

# print(prime_decomposition(25))
n = int(input())
p = prime_decomposition(n)
# print(p)

cnt = 0
for k in set(p):
    b = p.count(k)
    a = 1
    c = 1
    while c <= b:
        a += 1
        c += a
    cnt += a - 1

print(cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]*N
for i in range(1,N+1):
    print(A.index(i)+1,end=" ")

    

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
AA=[]
for i in range(N):
    AA.append([A[i],i+1])
AA.sort()
for j in range(N):
    print(AA[j][1],end=" ")
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))

L.sort()
X=0
for i in range(N):
  for k in range(N-(i+1)):
    j=i+1+k
    s=L[i]+L[j]
    d=max(L[i]-L[j],L[j]-L[i])
    lb=0
    ub=N-1
    while lb<ub:
      mn=(lb+ub)//2
      if L[mn]<=d:
        lb=mn+1
      else:
        ub=mn
    dmin=lb
    
    lb=0
    ub=N-1
    while lb<ub:
      mn=(lb+ub)//2
      if mn*2 != lb+ub:
        mn=mn+1
      if L[mn]>=s:
        ub=mn-1
      else:
        lb=mn
    smax=lb
    a=smax-dmin+1
    if dmin<=i and i<=smax:
      a-=1
    if dmin<=j and j<=smax:
      a-=1
    X+=a
print(int(X/3))

### FIXED CODE ###

N=int(input())
L=list(map(int, input().split()))

L.sort()
X=0
for i in range(N):
  for k in range(N-(i+1)):
    j=i+1+k
    s=L[i]+L[j]
    d=max(L[i]-L[j],L[j]-L[i])
    lb=0
    ub=N-1
    while lb<ub:
      mn=(lb+ub)//2
      if L[mn]<=d:
        lb=mn+1
      else:
        ub=mn
    dmin=lb
    
    lb=0
    ub=N-1
    while lb<ub:
      mn=(lb+ub)//2
      if mn*2 != lb+ub:
        mn=mn+1
      if L[mn]>=s:
        ub=mn-1
      else:
        lb=mn
    smax=lb
    a=smax-dmin+1
    if dmin<=i and i<=smax:
      a-=1
    if dmin<=j and j<=smax:
      a-=1
    X+=a
print(int(X/3))
### BUGGY CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = ((comb_i * (N - 1 + i) * 25) * pow(i, -1, mod) * pow(26, -1, mod)) % mod
  ans += comb_i
  
print(ans % mod)

### FIXED CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
div = pow(26, -1, mod)
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i) * pow(i, -1, mod)) % mod
  comb_i = (comb_i * 25 * div) % mod
  ans = (ans + comb_i) % mod
  
print(ans)
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
i=0
ans=1
flag=0
k=1e18
while(n>i):
	if(p[i]==0):
		flag=1
	i+=1
if(flag==1):
	print(0)
else:
	flag=0
	i=0			
	while(n>i):
		ans*=p[i]
		if(ans>k):
			flag=1
		i+=1		
	if( flag==1):
		print(-1)
	else:
		print(ans)
		


### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
i=0
ans=1
flag=0
k=1e18
while(n>i):
	if(p[i]==0):
		flag=1
	i+=1
if(flag==1):
	print(0)
else:
	flag=0
	i=0			
	while(n>i):
		ans*=p[i]
		if(ans>k):
			flag=1
			break
		i+=1		
	if( flag==1):
		print(-1)
	else:
		print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline


n_nodes, q_query = map(int, input().split())

edges = [[] for _ in range(n_nodes)]
for _ in range(n_nodes - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

queries = []
for _ in range(q_query):
    p, x = map(int, input().split())
    queries.append([p - 1, x])

# print(n_nodes, q_query)
# print(edges, queries)

res = [0 for _ in range(n_nodes)]
for node, point in queries:
    res[node] += point


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            res[v_next] += res[v]
            dfs(v_next, v)


dfs(0, None)

print(*res)


### FIXED CODE ###

#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 6)

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

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)
### BUGGY CODE ###

def makenetwork():
  for n in range(1,N+1):
    visited=set((n,))
    while visited:
      v=visited.pop()
      D[n].append(v)
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)

        
def main():
  makenetwork()
  #print(D)
  ans=[0]*(N+1)
  for n in range(1, N+1):
  	ans[n]=len(D[n]) - len(F[n]) - len(set(D[n])&set(B[n])) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[[] for n in range(N+1)]
  for m in range(M):
    a, b = map(int, input().split())
    F[a]+=[b]
    F[b]+=[a]
  B=[[] for n in range(N+1)]
  for k in range(K):
    c, d = map(int, input().split())
    B[c]+=[d]
    B[d]+=[c]
  D=[[] for n in range(N+1)]
  #print(F)
  #print(B)
  main()

### FIXED CODE ###

def makeRelation():
  visited=[False]*(N+1)
  g=0 # group
  for n in range(1,N+1):
    if visited[n]:
      continue
    q={n}
    D.append(set())
    while q:
      j=q.pop()
      for i in F[j]: # search for friend
        if not visited[i]:
          visited[i]=True
          q.add(i)
          D[g]|={i}
    g+=1
    
def main():
  makeRelation()
  #print(D)
  for g in D:
    for d in g:
      ans[d]=len(g) - len(F[d]) - len(g&B[d]) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[set() for n in range(N+1)]
  AB=[list(map(int, input().split())) for m in range(M)]
  for a,b in AB:
    F[a].add(b)
    F[b].add(a)
  B=[set() for n in range(N+1)]
  CD=[list(map(int, input().split())) for k in range(K)]
  for c,d in CD:
    B[c].add(d)
    B[d].add(c)
  D=[]
  #print(F)
  #print(B)
  ans=[0]*(N+1)
  main()
### BUGGY CODE ###

def get_primes(n=10**6):
    primes = [2]
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return primes + data
        primes.append(p)
        data = [d for d in data if d % p != 0]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes()
    lcm_pf = [0] * len(primes)
    a_pf = [[0] * len(primes) for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    L = 1
    for a in A:
        L = L * a // math.gcd(L, a)
    ans = 0
    for a in A:
        ans += L * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


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

import itertools
n, m, r = map(int, input().split())
distination = set(map(int, input().split()))
inf = 10 ** 9
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = inf
for p in itertools.permutations(distination):
    cost = 0
    for i in range(r-1):
        cost += d[p[i]-1][p[i+1]-1]
    ans = min(ans, cost)
print(ans)

### FIXED CODE ###

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

inf = 10 ** 18
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

import itertools
ans = 10 ** 18
for a in itertools.permutations(v):
    dis = 0
    for i in range(r-1):
        dis += d[a[i+1]-1][a[i]-1]
    ans = min(ans, dis)
print(ans)
### BUGGY CODE ###

X = input()
for i in range(10**5):
    X = X.replace("ST","")
print(len(X))

### FIXED CODE ###

X = input()
stack = []
for e in X:
    if e == "S":
        stack.append(e)
    elif stack == []:
        stack.append(e)
    elif stack[-1] == "T":
        stack.append(e)
    elif stack[-1] == "S":
        stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    L, R = map(int, input().split())
    A.append(list(range(L, R + 1)))

L = set(A[0])
for i in range(1, M):
    L = L & set(A[i])

print(len(L))


### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    L, R = map(int, input().split())
    if i == 0:
        Lmax = L
        Rmin = R
    else:
        Lmax = max(L, Lmax)
        Rmin = min(R, Rmin)

# L = set(A[0])
# for i in range(1, M):
#     L = L & set(A[i])

if Rmin-Lmax < 0:
    print(0)
else:
    print(Rmin-Lmax+1)
### BUGGY CODE ###

N = int(input())
A=[]
for j in range(N): 
    A.append([int(i) for i in input().split()])
    
for list in A:
    list.reverse()

day = 0
empty = [0] * N 

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in range(N):
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = 1
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][-1])-1][-1]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][-1])-1)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if sum(empty) == N:
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].pop(-1)

### FIXED CODE ###

import copy
import collections

N = int(input())
A=[]
for j in range(N): 
    A.append(collections.deque(int(i) for i in input().split()))

day = 0
empty = [0] * N 
s = [i for i in range(N)]

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in s:
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = None
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][0])-1][0]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][0])-1)
                s = copy.copy(q)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if not(0 in empty):
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].popleft()
### BUGGY CODE ###

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

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

A_dict = {}

#Aをhash
for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1


for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        #最小値がc以上なら何もしない
        if min(A_dict.keys()) >= c:
            break
        else:
            if A_dict[min(A_dict.keys())] == 1:
                del A_dict[min(A_dict.keys())]
                if c in A_dict:
                    A_dict[c] += 1
                else:
                    A_dict[c] = 1
            else:
                A_dict[min(A_dict.keys())] -= 1
                if c in A_dict:
                    A_dict[c] += 1
                else:
                    A_dict[c] = 1

ans = 0
for k, v in A_dict.items():
    ans += k * v
print(ans)

### FIXED CODE ###

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

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

A_dict = {}

#Aをhash
for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1


for i in range(M):
    b, c = map(int, input().split())
    if c in A_dict:
        A_dict[c] += b
    else:
        A_dict[c] = b

A_dict = sorted(A_dict.items(), key=lambda x: -x[0])


card = 0
ans = 0
for i in A_dict:
    if card == N:
        break
    elif card + i[1] > N:
        ans += (N - card) * i[0]
        break
    else:
        ans += i[0] * i[1]
        card += i[1]
print(ans)
### BUGGY CODE ###

from time import process_time
import sys

t1 = process_time()

input_list = list(sys.stdin.readline())
input_list.remove('\n')

#print("input_list created")

height_list = [0]
height = 0
for d in input_list:
    if d == '\\':
        height += -1
        height_list.append(height)
    if d == '/':
        height += 1
        height_list.append(height)
    if d == '_':
        height_list.append(height)

highest = max(height_list)
lowest = min(height_list)
flag = False
left_side_index = 0
right_side_index = 0
left_and_right_dict = {} # key = left_side_index, value = right_side_index
skip_indices = []
while highest != lowest:
    for i in range(len(height_list)):
        if i in skip_indices:
            continue
        else:
            if height_list[i] != highest:
                continue
            else:
                if i != len(height_list) - 1 and input_list[i] == '\\':
                    for k in range(i + 1, len(height_list)):
                        if height_list[k] != highest:
                            continue
                        else:
                            if input_list[k-1] == '/':
                                left_side_index = i
                                right_side_index = k
                                flag = True
                                break
                # Get the width of a puddle
                if flag:
                    left_and_right_dict[left_side_index] = right_side_index
                    for j in range(left_side_index, right_side_index):
                        skip_indices.append(j)
                    flag = False
    highest += -1

area_list = []
for left in sorted(left_and_right_dict.keys()):
    area = 0
    surface = height_list[left]
    for i in range(left, left_and_right_dict[left]):
        if input_list[i] == '\\':
            area += abs(surface - height_list[i+1]) - 0.5
        if input_list[i] == '/':
            area += abs(surface - height_list[i]) - 0.5
        if input_list[i] == '_':
            area += abs(surface - height_list[i])
    area_list.append(int(area))

print(sum(area_list))
if area_list != []:
    print(len(area_list), end = ' ')
    print(*area_list)
else:
    print(0)


### FIXED CODE ###

string = input()
height = 0
height_list = [[0, False]]
for s in string:
    if s == '\\':
        height += -1
    elif s == '/':
        height += 1
    else:
        pass
    height_list.append([height, False])

highest = 0
for i in range(1, len(height_list)):
    if height_list[i-1][0] < height_list[i][0] <= highest:
        height_list[i][1] = True
    highest = max(highest, height_list[i][0])

puddles = []
area = 0
surface_level = None

for i in range(len(height_list)-1, -1, -1):
    if surface_level != None:
        area += surface_level - height_list[i][0]
        if surface_level == height_list[i][0]:
            puddles += [area]
            surface_level = None
            area = 0
    if surface_level == None and height_list[i][1]:
        surface_level = height_list[i][0]

puddles = puddles[::-1]
print(sum(puddles))
print(len(puddles), *puddles)
### BUGGY CODE ###

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

for i in range(q):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
A = [0]*1000000

for i in a:
    A[i] += 1
    
ans = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    ans = ans+((c-b)*(A[b]))
    print(ans)
    A[c] += A[b]
    A[b] = 0
### BUGGY CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())
k = -1
def h_sort(list):
    h = []
    for v in list:
        heapq.heappush(h, v)
    return [heapq.heappop(h) for i in range(len(h))]

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job = h_sort(job)
job.reverse()


for x in job:
    s,t = x
    if k == -1 or k > t:
        k = t
    salary.append(t)

    if s - m > 0:
        if salary[0] > k:
            salary = h_sort(salary)
            k = -1
        del salary[0]
    else:
        m -= 1

print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

mod = 10**9+7
s = list(input())

s = s[::-1]

ls = len(s)

mod_13_list = [ (10**i) % 13 for i in range(6) ]

dp_list = [ 0 for i in range(13) ]
if  s[0] != "?":
    p = int(s[0])
    dp_list[p] += 1
else:
    for i in range(10):
        dp_list[i] += 1

t = 1
for i in range(1,ls):
    r = mod_13_list[t]
    t = ( t + 1 ) % 6
    new_dp_list = [ 0 for i in range(13) ]
    if s[i] != "?":
        p = int(s[i])
        q = ( p * r ) % 13
        for j in range(13):
            new_dp_list[(j+q)%13] += dp_list[j]
    
    else:
        for k in range(10):
            q = (k * ( 10 ** i) ) % 13
            for j in range(13):
                new_dp_list[(j+q)%13] += dp_list[j]
    
    dp_list = [ i % mod for i in new_dp_list ]

    
print(dp_list[5])


### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 10**9+7
s = list(input())[:-1]

s = s[::-1]

ls = len(s)

mod_13_list = [ (10**i) % 13 for i in range(6) ]

dp_list = [ 0 for i in range(13) ]
if  s[0] != "?":
    p = int(s[0])
    dp_list[p] += 1
else:
    for i in range(10):
        dp_list[i] += 1

t = 1
for i in range(1,ls):
    r = mod_13_list[t]
    t = ( t + 1 ) % 6
    new_dp_list = [ 0 for i in range(13) ]
    if s[i] != "?":
        p = int(s[i])
        q = ( p * r ) % 13
        for j in range(13):
            new_dp_list[(j+q)%13] += dp_list[j]
    
    else:
        for k in range(10):
            q = (k * r ) % 13
            for j in range(13):
                new_dp_list[(j+q)%13] += dp_list[j]
    
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[5])
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))

result = 0

for i in range(N-1):
    ans = 0
    for j in range(N-i-1):
        if H[i + j] >= H[i + j + 1]: 
            ans += 1
        else:
            break
    if result <= ans:
        result = ans

print(result)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = 0
result = 0

for i in range(N-1):
    if H[i] >= H[i+1] and i == N-2:
        ans += 1
        if result < ans:
            result = ans
    elif H[i] >= H[i+1]:
        ans +=1
    else:
        if result < ans:
            result = ans
        ans = 0

print(result)
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = sorted(list(map(int, input().split())))

BC_list = [tuple(map(int, input().split())) for _ in range(M)]
BC_list.sort(key=lambda x: x[1], reverse=True)

n_replace = 0
sum_target = 0
for B, C in BC_list:
    if n_replace + B <= N:
        for A in A_list[n_replace:n_replace+B]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                break
    else:
        remaining = N - n_replace
        for A in A_list[n_replace:n_replace+remaining]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                break
if n_replace < N:
    sum_target += sum(A_list[n_replace:])

# Output sumed A_list
print(sum_target)


### FIXED CODE ###

N, M = map(int, input().split())
A_list = sorted(list(map(int, input().split())))

BC_list = [tuple(map(int, input().split())) for _ in range(M)]
BC_list.sort(key=lambda x: x[1], reverse=True)

n_replace = 0
sum_target = 0
is_broken = False
for B, C in BC_list:
    if n_replace + B <= N:
        for A in A_list[n_replace:n_replace+B]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                is_broken = True
                break
    else:
        remaining = N - n_replace
        for A in A_list[n_replace:n_replace+remaining]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                is_broken = True
                break
    if is_broken is True:
        break
if n_replace < N:
    sum_target += sum(A_list[n_replace:])

# Output sumed A_list
print(sum_target)