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

import sys

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

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i, value in enumerate(order_F)]
    x -= distance[0]
    for i, value in enumerate(distance):
        if i == 0:
            continue
        if i % 2 == 0:
            side_sum += value
            for j in reversed(range(8001)):
                if side_DP[j]:
                    side_DP[j + value] = True
        else:
            vert_sum += value
            for j in reversed(range(8001)):
                if vert_DP[j]:
                    vert_DP[j + value] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

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

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    vert_last = 0
    side_last = 0
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(side_last+1)):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
            side_last += distance[i]
        else:
            vert_sum += distance[i]
            for j in reversed(range(vert_last+1)):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
            vert_last += distance[i]
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

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

from math import sqrt

N = int(input())
ps = []
for _ in range(N):
  ps.append(tuple(map(int, input().split())))
ps.sort()

def cross3(a, b, c):
  return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def cross(a, b, c, d):
  return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
  qs = []
  N = len(ps)
  for p in ps:
    # 一直線上で高々2点にする場合は ">=" にする
    while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  t = len(qs)
  for i in range(N-2, -1, -1):
    p = ps[i]
    while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  return qs

# キャリパー法(Rotating Calipers法)
# 凸多角形を回転しながら走査し、最遠点対を求める
def dist(a, b):
  return abs(a[0]-b[0]) + abs(a[1]-b[1])

def rotating_calipers(ps):
  qs = convex_hull(ps)
  n = len(qs)
  if n == 2:
    return dist(qs[0], qs[1])
  i = j = 0
  for k in range(n):
    if qs[k] < qs[i]: i = k
    if qs[j] < qs[k]: j = k
  res = 0
  si = i; sj = j
  while i != sj or j != si:
    res = max(res, dist(qs[i], qs[j]))
    if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
      i = (i + 1) % n
    else:
      j = (j + 1) % n
  return res

print(rotating_calipers(ps))

### FIXED CODE ###

from math import sqrt

N = int(input())
ps = set()
for _ in range(N):
  ps.add(tuple(map(int, input().split())))
ps = list(ps)
ps.sort()

def cross3(a, b, c):
  return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def cross(a, b, c, d):
  return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
  qs = []
  N = len(ps)
  for p in ps:
    # 一直線上で高々2点にする場合は ">=" にする
    while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  t = len(qs)
  for i in range(N-2, -1, -1):
    p = ps[i]
    while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  return qs

# キャリパー法(Rotating Calipers法)
# 凸多角形を回転しながら走査し、最遠点対を求める
def dist(a, b):
  return abs(a[0]-b[0]) + abs(a[1]-b[1])

def rotating_calipers(ps):
  qs = convex_hull(ps)
  n = len(qs)
  if n == 2:
    return dist(qs[0], qs[1])
  i = j = 0
  for k in range(n):
    if qs[k] < qs[i]: i = k
    if qs[j] < qs[k]: j = k
  res = 0
  si = i; sj = j
  while i != sj or j != si:
    res = max(res, dist(qs[i], qs[j]))
    if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
      i = (i + 1) % n
    else:
      j = (j + 1) % n
  return res

if len(ps) == 1:
  print(0)
elif len(ps) == 2:
  print(dist(ps[0], ps[1]))
else:
  print(rotating_calipers(ps))
### BUGGY CODE ###

n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = h // a
    if h % a != 0:
        num += 1
    xh[i][1] -= num * a
    for j in range(i + 1, len(xh)):
        if xh[j][0] > x + 2 * d:
            break
        if xh[j][1] > 0:
            xh[j][1] -= num * a
    cnt += num
print(int(cnt))

### FIXED CODE ###

from math import ceil
from bisect import bisect_right
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)
### BUGGY CODE ###

from math import sqrt
import re


def gcd(a, b):
    dividend, divisor = max(a, b), min(a, b)
    while True:
        dividend, divisor = divisor, dividend % divisor
        if divisor == 0:
            return dividend


def int_check(n):
    n_type = type(n)
    if n_type != int:
        n_type_str = re.search(r'\'.+\'', str(n_type)).group()
        raise TypeError(n_type_str + ' object cannot be interpreted as an integer')


def eratosthenes(n):
    int_check(n)
    if n == 1:
        return []

    int_list = list(range(2, n+1))
    bottom_index = 0

    while int_list[bottom_index] <= sqrt(n):
        prime = int_list[bottom_index]
        bottom_index += 1
        top_index = bottom_index

        for num in int_list[bottom_index:]:
            if num % prime != 0:
                int_list[top_index] = num
                top_index += 1

        del int_list[top_index:]

    return int_list


def naive_method(n):
    int_check(n)
    if n == 1:
        return []

    prime_divisors = []
    for prime in eratosthenes(int(sqrt(n))):
        if n % prime == 0:
            remain_factor = n
            exponent = 0
            while remain_factor % prime == 0:
                remain_factor //= prime
                exponent += 1
            prime_divisors.append((prime, exponent))
            prime_divisors.extend(naive_method(remain_factor))

    prime_factors = []
    if len(prime_divisors) == 0:
        prime_factors.append((n, 1))
    else:
        prime_divisors.append((float('inf'), -float('inf')))
        prime_divisors.sort(key=lambda t: t[0])
        current_factor, max_exponent = prime_divisors[0]
        for factor in prime_divisors:
            if factor[0] == current_factor:
                max_exponent = max(max_exponent, factor[1])
            else:
                prime_factors.append((current_factor, max_exponent))
                current_factor, max_exponent = factor

    return prime_factors


def main():
    a, b = map(int, input().split())
    print(len(naive_method(gcd(a, b))) + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
from math import sqrt, ceil

A, B = map(int, input().split())
gcd_ = gcd(A, B)

count = 1
for i in range(2, ceil(sqrt(gcd_)) + 1):
    if gcd_ % i == 0:
        count += 1
        while gcd_ % i == 0:
            gcd_ /= i

if gcd_ != 1:
    count += 1

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

n,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(max(dp[n]))

### FIXED CODE ###

n,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(max(dp[n]))
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]

ans = 0
for a in set(A):
    cnt = A.count(a)
    if a == cnt: continue
    elif a < cnt: ans += cnt-a
    elif a > cnt: ans += cnt
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()

ans = 0
cnt = 1

if n ==1:
    if a[0] == 1: 
        print(0)
        exit()
    else:
        print(1)
        exit()
 

for i in range(n-1):
    if a[i] == a[i+1]:cnt+=1
    else:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
        cnt = 1
    if i+1 == n-1:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
print(ans)
### BUGGY CODE ###

N,Ma,Mb=map(int, input().split())
A = []
B = []
C = []
for i in range(N):
  a,b,c=map(int, input().split())
  A.append(a)
  B.append(b)
  C.append(c)
sa = sum(A)
sb = sum(B)

dp = [[[10000]*(sb+1) for _ in range(sa+1)] for _ in range(N+1)]
dp[0][0][0] = 0

ta = 0
tb = 0
for i in range(N):
  a = A[i]
  b = B[i]
  for j in range(sa):
    for k in range(sb):
      if j - a >= 0 and k - b >= 0:
        dp[i+1][j][k] = min(dp[i][j-a][k-b]+C[i], dp[i][j][k])
      else:
        dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

dnp = dp[N]
ans = 10000
for i in range(sa):
  for j in range(sb):
    if Ma * (j+1) == Mb * (i+1):
      ans = min(ans, dnp[i+1][j+1])
if ans == 10000:
  ans = -1
print(ans)

### FIXED CODE ###

N,Ma,Mb=map(int, input().split())
A = []
B = []
C = []
for i in range(N):
  a,b,c=map(int, input().split())
  A.append(a)
  B.append(b)
  C.append(c)
sa = sum(A)
sb = sum(B)

dp = [[[10000]*(sb+1) for _ in range(sa+1)] for _ in range(N+1)]
dp[0][0][0] = 0

ta = 0
tb = 0
for i in range(N):
  a = A[i]
  b = B[i]
  for j in range(sa):
    for k in range(sb):
      if j - a >= 0 and k - b >= 0:
        dp[i+1][j][k] = min(dp[i][j-a][k-b]+C[i], dp[i][j][k])
      else:
        dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

ans = 10000
for i in range(1, sa+1):
  for j in range(1, sb+1):
    if Ma * j == Mb * i:
      ans = min(ans, dp[N][i][j])
if ans == 10000:
  ans = -1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
lis = []
for i in range(M):
    B ,C = map(int, input().split())
    if C > A[N-1]:
        for j in range(B):
            A.append(C)
        A.sort(reverse=True)
ans = 0
for i in range(N):
    ans += A[i]
print(ans)


### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC_list = []
BC_sorted = sorted(BC,key=itemgetter(1) ,reverse = True)

for i in BC_sorted:
    BC_list += [i[1]] * i[0]
    if len(BC_list) > N:
        break

Answer = 0
A += BC_list
ALL = sorted(A, reverse = True)

for i in range(N):
    Answer += ALL[i]
print(Answer)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
table=[-1]*n
edges=[[] for i in range(n)]
costs=[n]*n
for i in range(m):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)
def dfs(now,pre,cost):
    if costs[now]>cost:
        costs[now]=cost
        table[now]=pre+1
        for i in edges[now]:
            dfs(i,now,cost+1)
dfs(0,0,0)
if -1 not in table[1:]:
    print("Yes")
    for i in range(1,n):
        print(table[i])
else:print("No")

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline

n,m=map(int,input().split())
edges=[[] for i in range(n)]
table=[-1]*n
for i in range(m):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)
l=[0]
print()
from collections import deque as que
q=que([(-1,0)])
p=que()
flag=1
ok=0
while flag:
    flag=0
    while len(q):
        flag=1
        pre,now=q.pop()
        if table[now]==-1:
            ok+=1
            table[now]=pre+1
            for i in edges[now]:
                if table[i]==-1:
                    p.append((now,i))
    p,q=q,p






if ok==n:
    print("Yes")
    for i in range(1,n):
        print(table[i])
else:print("No")
### BUGGY CODE ###

def main():
    n = int(input())
    A = []
    B = []
    C = []
    for _ in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(a + b)
    ans = 0
    isA = True
    while C:
        index = C.index(max(C))
        C.pop(index)
        if isA:
            ans += A[index]
        else:
            ans -= B[index]
        isA = not isA
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = []
    B = []
    C = {}
    for i in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        C[str(i)] = a + b
    ans = 0
    isA = True
    for k, v in sorted(C.items(), key=lambda x: -x[1]):
        if isA:
            ans += A[int(k)]
        else:
            ans -= B[int(k)]
        isA = not isA
    print(ans)


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

from collections import deque
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    S.append(s)

def DFS(y,x,S):
    m=[[0]*W for _ in range(H)]
    d=deque([])
    d.append((y,x,0))
    ans=0
    while d:
        p,q,n=d.popleft()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='#':
    
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                ans+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='#':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='#':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='#':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='#':
                    d.append((p,q-1,n+1))
    return ans

total=0
for i in range(H):
    for j in range(W):
        total+=DFS(i,j,S)

print(total)
                

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    S.append(s)
m=[[0]*W for _ in range(H)]
def DFS(y,x,S):

    d=deque([])
    d.append((y,x,0))
    white=0
    black=0
    while d:
        p,q,n=d.popleft()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='#':
                black+=1
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                white+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='#':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='#':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='#':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='#':
                    d.append((p,q-1,n+1))
    return white,black

total=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            continue
        elif m[i][j]==1:
            continue
        else:
            w,b=DFS(i,j,S)
            total+=w*b

print(total)
### BUGGY CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    sum=0
    col=[-1 for i in range(n)]
    for i in range(n):
        if col[i]==1:
            continue
        for j in range(i+1,n):
            if a[i]%a[j]==0:
                col[i]=1
            if a[j]%a[i]==0:
                col[j]=1
        if col[i]==-1:
            sum+=1


    print(sum)
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    max=a[-1]
    check=[0 for i in range(max+10)]
    sum=0
    #print(a)
    if len(a)==1:
        print(1)
        exit()
    if a[0]==1:
        if a[1]==1:
            print(0)
        else:
            print(1)
        exit()
    for i in range(n):
        if check[a[i]]==0:
            sum+=1
            j=1
            x=a[i]*j
            while x<max+1:
                check[x]=1
                j+=1
                x=a[i]*j
            if i<n-1 and a[i+1]==a[i]:
                sum-=1
        else:
            continue
    print(sum)
        
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
for i in range(1,M+1):
    AB2 += AB[i]
    heapq.heapify(AB2)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
### BUGGY CODE ###

n,k=map(int,input().split())
ans=0
## a<b and k>0
ans+=(n-k)*(n-k+1)//2

#print(ans)
## a>b
for i in range(k,n+1):
    for j in range(1,i):
        if i%j>=k:
            ans+=1

print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
if k==0:
    print(n*n)
    exit()
ans=0
for i in range(k+1,n+1):
    ans+=((n+1)//i)*(i-k)+max(0,((n+1)%i-k))
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
x = [list(map(int,input().split())) for i in range(q)]
for i in range(q):
    cnt = 0
    t = s[x[i][0]-1:x[i][1]]
    for i in range(len(t)-1):
        if t[i]=="A" and t[i+1]=="C":
            cnt += 1
    print(cnt)


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
x = [list(map(int,input().split())) for i in range(q)]
cnt = 0
res = [0]
for i in range(1,len(s)):
    if s[i-1]=="A" and s[i]=="C":
        cnt += 1
    res.append(cnt)
for j in range(q):
    print(res[x[j][1]-1]-res[x[j][0]-1])
### BUGGY CODE ###

# coding=utf-8

INF = 10**9 + 1
n = int(input())
V = []

for _ in range(n):
    line = input().split(" ")
    V.append((int(line[0]), int(line[1])))

def cost(vi, ui):
    v = V[vi]
    u = V[ui]
    return min(abs(v[0]-u[0]), abs(v[1]-u[1]))

mincost = [INF for _ in range(n)]
used = [False for _ in range(n)]

mincost[0] = 0
ret = 0

while True:
    v = -1
    for u in range(n):
        if not used[u] and (v==-1 or mincost[u]<mincost[v]):
            v = u
    if v==-1:
        break

    used[v] = True
    ret += mincost[v]

    for u in range(n):
        mincost[u] = min(mincost[u], cost(v,u))

print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
ax = []
ay = []
for i in range(n):
    x,y = map(int, input().split())
    ax.append((x,i))
    ay.append((y,i))

ax.sort()
ay.sort()

edge = []
for i in range(n-1):
    v = ax[i][1]
    u = ax[i+1][1]
    c = abs(ax[i][0]-ax[i+1][0])
    edge.append((c,v,u))

    v = ay[i][1]
    u = ay[i+1][1]
    c = abs(ay[i][0]-ay[i+1][0])
    edge.append((c,v,u))

edge.sort()



class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return

        if x<y:
            self.par[y] = x
        else:
            self.par[x] = y
    def same(self, x, y):
        return self.find(x) == self.find(y)

t = UnionFind(n)
res = 0
for e in edge:
    cost = e[0]
    v = e[1]
    u = e[2]

    if not t.same(v,u):
        # print((v,u,cost))
        t.unite(v,u)
        res += cost

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

N = int(input())
S = list(input())

Rcnt = 0
Gcnt = 0
Bcnt = 0

excep = 0

for i in S:
    if i == 'R':
        Rcnt += 1
    elif i == 'G':
        Gcnt += 1
    elif i == 'B':
        Bcnt += 1

for i in range(len(S)):
    for j in range(1, len(S)):
        if i+j+j < len(S):
            if S[i] != S[i+j] and S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                # print(S[i], S[i+1], S[i+2])
                excep += 1

RGBcalc = Rcnt * Gcnt * Bcnt

print(RGBcalc - excep)

### FIXED CODE ###



N = int(input())
S = list(input())

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)
### BUGGY CODE ###

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

from collections import deque
import bisect

cards = sorted(cards)

for _ in range(m):
    b,c = map(int,input().split())

    index = bisect.bisect_left(cards,c)

    for i in range(index):
        if i+1>b:
            continue
        cards.pop(0)
        cards.insert(index-1,c)


print(sum(cards))


### FIXED CODE ###

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

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

print(ans)