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

N, M = map(int, input().split())
P = [i for i in range(N)]
D = [0] * N
C = [1] * N

def par(a):
    if a == P[a]:
        return a
    p = par(P[a])
    d = D[P[a]]
    P[a] = p
    D[a] += d
    return p

def dist(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb:
        return D[b] - D[a]
    return 1 << 30

def unite(a, b, d):
    if par(a) == par(b):
        return
    if C[P[a]] < C[P[b]]:
        a, b = b, a
    D[P[b]] = D[a] + d - D[b]
    P[P[b]] = P[a]

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    dd = dist(l, r)
    if dd == 1<<30:
        unite(l, r, d)
    else:
        if d != dd:
            print("No")
            break
else:
    print("Yes")

### FIXED CODE ###

N, M = map(int, input().split())
P = [i for i in range(N)]
D = [0] * N
C = [1] * N

def par(a):
    if a == P[a]:
        return a
    p = par(P[a])
    d = D[P[a]]
    P[a] = p
    D[a] += d
    return p

def dist(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb:
        return D[b] - D[a]
    return 1 << 30

def unite(a, b, d):
    if par(a) == par(b):
        return
    if C[P[a]] < C[P[b]]:
        a, b, d = b, a, -d
    C[P[a]] += C[P[b]]
    D[P[b]] = D[a] + d - D[b]
    P[P[b]] = P[a]

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    dd = dist(l, r)
    if dd == 1<<30:
        unite(l, r, d)
    else:
        if d != dd:
            print("No")
            break
else:
    print("Yes")
### BUGGY CODE ###

from collections import deque
X,Y,A,B,C=map(int,input().split())
p=deque(sorted(map(int,input().split())))
q=deque(sorted(map(int,input().split())))
r=deque(sorted(map(int,input().split())))
ans=[]
for i in range(X):
	ans.append(p.pop())
for i in range(Y):
	ans.append(q.pop())
for i in r:
	if i>min(ans):
		ans.remove(min(ans))
		ans.append(i)
print(sum(ans))


### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=sorted(map(int,input().split()))
q=sorted(map(int,input().split()))
r=sorted(map(int,input().split()))
ans=[]
ans+=p[A-X:]
ans+=q[B-Y:]
ans.sort()
j=0
k=0
for i in ans:
	if len(r)>1:
		k=r[-1]
	elif len(r)==1:
		k=r[0]
	else:
		break
	if i<k:
		ans[j]=r.pop()
		j+=1
	else:
		break
print(sum(ans))
### BUGGY CODE ###

# 先頭と末尾を保ちつつ
s = input()
q = int(input())
x, y = [], []
r = 0
for _ in range(q):
    query = input().split()
    if query[0] == "1":
        r += 1
        # これ遅いか？
        x, y = y[::-1], x[::-1]
    elif query[0] == "2":
        f, c = query[1], query[2]
        if f == "1":
            # x.append(c)
            x = x[::-1]
            x.append(c)
            x = x[::-1]
        elif f == "2":
            y.append(c)
if r % 2 == 1:
    s = s[::-1]
print("".join(x) + s + "".join(y))


### FIXED CODE ###

# 先頭と末尾を保ちつつ
from collections import deque

s = input()
q = int(input())
x, y = deque(), deque()
r = 0
for _ in range(q):
    query = input().split()
    if query[0] == "1":
        r += 1
        x, y = y, x
    elif query[0] == "2":
        f, c = query[1], query[2]
        if f == "1":
            if r % 2 == 0:
                x.appendleft(c)
            else:
                x.append(c)
        elif f == "2":
            if r % 2 == 1:
                y.appendleft(c)
            else:
                y.append(c)

if r % 2 == 1:
    s = s[::-1]
    x = reversed(x)
    y = reversed(y)
print("".join(x) + s + "".join(y))
### BUGGY CODE ###

S = list(map(int,input()))

counter = 0
amari = [0]*2019

s = 0
for i in range(len(S)):
    if S[len(S)-i-1] == 0:
        continue
    else:
        s += S[len(S)-i-1] * 10**i
        s = s % 2019
        amari[s] += 1

for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2

counter += amari[0]

print(int(counter))

### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

N = int(input())
A = (input().split())
B = []
C = 0
for i in range(N + 1):
  B.append(A.count(str(i)))
  C += int(B[i] * (B[i] - 1) / 2)
for j in range(N):
  if B[int(A[j])] > 1:
    D = C + 1 - B[int(A[j])]
    print(D)
  else:
    print(0)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
B = collections.Counter(A)
L = {key:(B[key] * (B[key] - 1) // 2) for key in B}
total = sum(L.values())
#print(f"A = {A}\nB = {B}\nL = {L}\ntotal = {total}")
[print(total if L[i] == 0 else total - L[i] + ((B[i] - 1) * (B[i] - 2) // 2)) for i in A]
### BUGGY CODE ###

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

mod = 10**9+7

dp = [0] * (n+1)
dp[0] = 1

for i in range(1,n+1):
    #print(i)
    if i in ai:
        dp[i] = 0
    else:
        if i == 1:
            dp[i] = dp[i-1] % mod
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod
#    dp[i+1] = dp[i-1] + dp[i]
            
print(dp[n]%mod)

### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]

ans = 0

now = 0

dp = [0]*(N+1)
disable = [0]*(N+1)

for i in range(M):
    #print(i)
    disable[a[i]] = 1
    

waru = 10**9+7
dp[0] = 1

for i in range(1,N+1):
    if disable[i] == 1:
        dp[i] = 0
    else:
        dp[i] = ( dp[i-1] + dp[i-2] )  % waru

print(dp[N])
### BUGGY CODE ###

n = int(input())

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
ans = 0
for k in range(1, n+1):
    d = primeFactor(k)
    temp = 1
    for _, v in d.items():
        temp *= (v+1)
    ans += k*temp
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
    m = n//i
    ans += (m*(m+1)//2)*i
print(ans)
### BUGGY CODE ###

def solve(n, xs, k):
    ss = [0] + [abs(a - b) for (a, b) in zip(xs + [0], [0] + xs)]
    for i in range(1, n + 1):
        ss[i + 1] += ss[i]
    cost2 = [abs(a - b) for (a, b) in zip(xs[1:] + [0], [0] + xs[:n - 1])]
    return ss[n + 1] - ss[k + 2] + ss[k] + cost2[k]

if __name__ == "__main__":
    n = int(input())
    xs = [int(s) for s in input().split()]
    for i in range(n):
        print(solve(n, xs, i))


### FIXED CODE ###

def solve(n, xs):
    ss = [0] + [abs(a - b) for (a, b) in zip(xs + [0], [0] + xs)]
    for i in range(1, n + 1):
        ss[i + 1] += ss[i]
    cost2 = [abs(a - b) for (a, b) in zip(xs[1:] + [0], [0] + xs[:n - 1])]
    for k in range(n):
        yield ss[n + 1] - ss[k + 2] + ss[k] + cost2[k]

if __name__ == "__main__":
    n = int(input())
    xs = [int(s) for s in input().split()]
    for ans in solve(n, xs):
        print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]

fibo=[0]*(n+1)
fibo[0]=1
fibo[1]=1 if 1 not in a else 0
mod=10**9+7
for i in range(2,n+1):
  if i in a:
    continue
  fibo[i]=(fibo[i-2]+fibo[i-1])%mod

print(fibo[-1])

### FIXED CODE ###

import sys
mod = 10**9+7

def main():
    n, m = map(int, input().split(' '))
    if m > 0:
        aaa = set(map(int, sys.stdin))
    else:
        aaa = set()
 
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in aaa else 0
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()
### BUGGY CODE ###

import math
A,B=map(int,input().split())
#nの約数を全て求める
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
answers=[]
a=divisor(A)
b=divisor(B)
for a_ in a:
    if a_ in b:
        answers.append(a_)
n = len(answers)
numbers=[]
for i in range(2 ** n):
    number = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            number.append(answers[j])  # フラグが立っていたら bag に果物を詰める
    numbers.append(number)
del numbers[0]
answer=0
for number in numbers:
    ans=0
    for m in range(len(number)-1):
        for n in range(m+1,len(number)):
            a=math.gcd(number[m],number[n])
            if a!=1:
                ans=1
                break
    if ans==0:
        answer=max(answer,len(number))
print(answer)


### FIXED CODE ###

A,B=map(int,input().split())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
a=make_divisors(A)
b=make_divisors(B)
kouyakusuu=set(a)&set(b)
out=[]
kouho=sorted(list(kouyakusuu))
del kouho[0]
for a in range(len(kouho)-1):
    for b in range(a+1,len(kouho)):
        if kouho[b]%kouho[a]==0:
            out.append(kouho[b])
answer=set(out)
print(len(kouho)+1-len(answer))
### BUGGY CODE ###

def myinput(rownum):
    res = []
    for i in range(rownum):
        temp = input().split(" ")
        res += temp
    return res

def main():
    r = myinput(2)
    n = r[0]
    a = r[1:]
    ilist = [str(i+1) for i in range(len(a))]
    res = []
    for i in ilist:
        res.append(str(a.index(i) + 1))
    print(" ".join(res))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    n = input()
    a = input().split(" ")
    # r = ""
    # for i in range(int(n)):
    #     r += str(a.index(str(i+1)) + 1) + " "
    # print(r[:-1])
    a = [(a[i],str(i+1)) for i in range(len(a))]
    a = list(map(lambda x:x[1],sorted(a,key=lambda x:int(x[0]))))
    print(" ".join(a))

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

N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得

import collections
counted = collections.Counter(s)
#最頻値が同値である場合全て出力したい
#頻出数ではなく、文字だけ出力したい
ret = [letter for letter,count in counted.most_common() if count == counted.most_common()[0][1]]
new_ret=sorted(ret)
for i in range(len(new_ret)):
    print(new_ret[i])# ['a', 'c']

### FIXED CODE ###

from collections import Counter


N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得
ans=[]

counted = Counter(s)#
counted_sort=counted.most_common()

for i in range(len(counted_sort)):
    if counted_sort[i][1]==counted_sort[0][1]:
        ans.append(counted_sort[i][0])


[print(i) for i in sorted(ans)]
### BUGGY CODE ###

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

xa = []
xb = []
count = 0
for i in x:
    if i > a:
        xa.append(i-a)
    elif i < a:
        xb.append(i-a)
    else:
        count += 1
ans = 0
if len(xa) == 0 or len(xb) == 0:
    print(2**count-1)
else:
    for i in range(1,len(xa)+1):
        for j in range(1,len(xb)+1):
            for k in itertools.combinations(xa,i):
                for l in itertools.combinations(xb,j):
                    if sum(k)+sum(l) == 0:
                        ans += 1
    if ans == 0:
        print(0)
    elif count == 0:
        print(ans)
    else:
        print((ans+1)*2**count-count)

### FIXED CODE ###

n,a = map(int, input().split())
x = list(map(int,input().split()))
x = [i-a for i in x]

d = {}
d[0] = 1
for i in x:
    for j,k in list(d.items()):
        d[j+i] = d.get(j+i,0)+k
print(d[0]-1)
### BUGGY CODE ###

D=60
n,k,*l=map(int,open(0).read().split())
to=[[0]*n for _ in range(D)]
for i in range(n):
  to[0][i]=l[i]-1
for i in range(D-1):
  for j in range(n):
    to[i+1][j]=to[i][to[i][j]]
a=0
for i in range(D):
  if k%2:
    a=to[i][a]
  k//=2
print(a+1)

### FIXED CODE ###

f=lambda:map(int,input().split())
n,k=f()
a=list(f())
lv=[-1]*n
lv[0]=0
p=0
for i in range(n):
  t=a[p]-1
  if lv[t]>=0:
    l,r=lv[t],i+1
    break
  lv[t]=i+1
  p=t
print(lv.index(l+(k-l)%(r-l) if k>l else k)+1)
### BUGGY CODE ###

K = int(input())
Que = list(range(1,10))
for i in range(K):
    x = Que.pop(0)
    a = x%10
    if a !=0:
        Que.append(10*x +a -1)
    Que.append(10*x +a )
    if a != 9:
        Que.append(10*x +a +1)
print(x)


### FIXED CODE ###

import queue
K = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(K):
    x = q.get()
    a = x%10
    if a !=0:
        q.put(10*x +a -1)
    q.put(10*x +a )
    if a != 9:
        q.put(10*x +a +1)
print(x)
### BUGGY CODE ###

n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [[] for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
ans = []
for i in range(n): #自分がi
    data = [0 for i in range(n)] #友人は1
    count = 0
    data[i] = 2
    for j in ab[i]:
        data[j] = 1
    for j in cd[i]:
        data[j] = -1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = []
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0):
                    data[frfr] = 1
                    new.append(frfr)
                    count += 1
                elif(data[frfr] == -1):
                    new.append(frfr)
        if(len(new)==0):
            break
        else:
            new_friends.append(new)
    ans.append(count)

print(*ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [set([]) for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].add(d-1)
    cd[d-1].add(c-1)
    
ans = [0 for i in range(n)]
data = [0 for i in range(n)] #見たら1
for i in range(n): #自分がi
    if(data[i] != 0): #もう見てたら必要なし
        continue
    data[i] = 1 #iの人を見る
    data2 = ab[i] + [i]
    data2 = set(data2)
    for j in ab[i]:
        data[j] = 1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = [] #次の深さのリスト
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0): #見てなかったら加える
                    data[frfr] = 1 
                    new.append(frfr) #次の深さのリストに足す
                    data2.add(frfr) #グラフに足す
        if(len(new)==0):
            break
        else:
            new_friends.append(new)

    sam = len(data2)
    for j in data2:
        count = sam
        ans[j] = count - len(ab[j]) - len(cd[j] & data2) - 1 #自分と友達を除く


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

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
    s=list(input())
    l.append(s+s)
ans=0
for i in range(n):
    f=0
    for h in range(n):
        for w in range(n):
            #0,0+i 1,1+i h,h+i
            if l[h][w+i]!=l[w][h+i]:
                f+=1
    if f==0:
        ans+=1
print(ans*n)


### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
    s=list(input())
    l.append(s+s)
ans=0
for i in range(n):
    f=0
    for h in range(n):
        for w in range(n):
            #0,0+i 1,1+i h,h+i
            if l[h][w+i]!=l[w][h+i]:
                f+=1
    if f==0:
        ans+=1
print(ans*n)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
T = list(set(A))
L = []
for i in range(len(T)) :
    ti = T[i]
    t = A.count(ti)
    if t < ti :
        L.append(t)
    else :
        L.append(t - ti) 
print(sum(L))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1
answer = 0
for key, value in D.items() :
    if key > value :
        answer += value
    else :
        answer += value-key
print(answer)
### BUGGY CODE ###

monster_num, special_num = map(int ,input().split())
monster_list = list(map(int, input().split()))

monster_list = sorted(monster_list)
 
for _ in range(special_num):
  monster_list = monster_list[:-1]
  
print(sum(monster_list))

### FIXED CODE ###

monster_num, special_num = map(int ,input().split())
monster_list = list(map(int, input().split()))
 
monster_list = sorted(monster_list)[::-1]
 
monster_list = monster_list[special_num:]
  
print(sum(monster_list))
### BUGGY CODE ###

N = int(input())
a = []
res = 0
for _ in range(N):
  a.append(int(input()))

hasGreaterBefore = set()
max_v, min_v = 0, 2e5

for e in a:
    if max_v < e:
        max_v = e
    else:
        hasGreaterBefore.add(e)

for num in range(N, 0, -1):
    if num in hasGreaterBefore:
        eidx = a.index(num)
        hasGreaterBefore.remove(num)
        if num > a[0]:
            hasGreaterBefore.add(a[0])
        if eidx != 0:
            a.pop(eidx)
            a = [num] + a
            res += 1

print(res)


### FIXED CODE ###

N = int(input())
a = [0]
for _ in range(N):
  a.append(int(input()))

Q = [0 for i in range(N + 1)]
for i in range(N + 1):
    Q[a[i]] = i
ans = 1
num = 1

for idx in range(2, len(Q)):
    if Q[idx - 1] < Q[idx]:
        num += 1
    else:
        ans, num = max(num, ans), 1

print(N - max(num, ans))
### BUGGY CODE ###

A, B = map(int, input().split())
 
while A!=B:
  if A < B:
    A += A
  else:
    B += B
 
print(A)

### FIXED CODE ###

from fractions import gcd


def lcm(x, y):
    return (x * y) // gcd(x, y)


A, B = map(int, input().split())
print(lcm(A, B))
### BUGGY CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = Counter(a)
if len(c.keys()) <= k:
    print(0)
    exit()
else:
    ans = 0
    lis = list(c.values())
    lis.sort()
    while(len(lis) > k):
        ans += lis.pop(0)
print(ans)


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = Counter(a)
if len(c.keys()) <= k:
    print(0)
    exit()
else:
    ans = 0
    lis = list(c.values())
    lis.sort()
    l = len(lis) - k
    for i in range(l):
        ans += lis[i]
print(ans)
### BUGGY CODE ###

n,q = list(map(int, input().split()))
s = list(str(input()))
lr = [list(map(int, input().split())) for _ in range(q)]

for i in lr:
    ans = 0
    ch = "B"
    for j in range(i[0]-1, i[1]):
        if s[j] == "A":
            ch = "A"
        elif ch == "A" and s[j] == "C":
            ans += 1
            ch = "B"

    print(ans)

### FIXED CODE ###

h,n = list(map(int, input().split()))
st = str(input())
a = [list(map(int, input().split())) for _ in range(n)]

o = "B"
b = []
c = 0
for i in range(len(st)):
    sti = st[i]
    if sti == "A":
        o = "A"
        b.append(c)
    elif sti == "C" and o == "A":
        o = "C"
        c += 1
        b.append(c)
    else:
        o = "B"
        b.append(c)

for a1,b1 in a:
    print(b[b1-1] - b[a1-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
import time



"""
def make_table_min(n, m):
    Table = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    c = 10
    for i in range(n):
        rem = np.random.randint(1,m+1)
        Table.remove(rem)
    return Table

"""

def make_table(n, m):
    Table = [None]*n
    for i in range(n):
        rem = np.random.randint(1,m+1)
        Table[i] = rem
    return Table

t0 = time.time()
n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Sum_cor = []
for i in range(10000000000):
    if m >=6:
        Table = make_table(n,m)
    else:
        Table = make_table(n,m)
    Table.sort()
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)
    t1 = time.time()
    if t1-t0 >1.9:
        print(max(Sum_cor))
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

from itertools import combinations_with_replacement as CwR



n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Tables = list(CwR(range(1,m+1),n))
Sum_cor = []
for Table in Tables:
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)

print(max(Sum_cor))
### BUGGY CODE ###

N, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_c_list = []
for _ in range(M):
    b, c = list(map(int, input().split()))
    b_c_list.append((b, c))
b_c_list = sorted(b_c_list, key=lambda x: x[1], reverse=True)

def seach_index(l, r, values, t):
    if r - l <= 1:
        return r

    if t < values[(r+l)//2]:
        return seach_index(l, (r+l)//2, values, t)
    else:
        return seach_index((r+l)//2, r, values, t)

class Tree:
    def __init__(self, a_list):
        self.values = sorted(a_list)
        self.len = len(a_list)

    def get_min_value(self):
        return self.values[0]
    
    def replace(self, value):
        poped = self.values.pop(0)

        gi = seach_index(0, self.len - 2, self.values, value)
        self.values.insert(gi, value)

tree = Tree(a_list)
for b, c in b_c_list:
    if c <= tree.get_min_value():
        break
    for _ in range(b):
        if tree.get_min_value() < c:
            tree.replace(c)

print(sum(tree.values))


### FIXED CODE ###

N, M = list(map(int, input().split()))
a_list = sorted(list(map(int, input().split())))
b_c_list = []
for _ in range(M):
    b, c = list(map(int, input().split()))
    b_c_list.append((b, c))
b_c_list = sorted(b_c_list, key=lambda x: x[1], reverse=True)

def b_c_gen():
    for b, c in b_c_list:
        for _ in range(b):
            yield c

total = 0
for i, c in enumerate(b_c_gen()):
    if i >= N:
        break
    if a_list[i] >= c:
        i -= 1
        break
    total += c
i += 1

if i < N:
    total += sum(a_list[i:])
print(total)