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

import re
n = int(input())
d = input().split()
m = int(input())
t = input().split()

if len(d) < len(t):
    print("NO")
    exit()

t_size = len(t)
t_sorted = sorted(t)
reg = [] 
for i in range(0, t_size-2):
    if t_sorted[i] == t_sorted[i+1]:
        reg.append(t_sorted[i])
    else:
        reg.append(t_sorted[i]+".*")

reg.append(t_sorted[t_size-1])

reg_pattern = re.compile("".join(reg));
match = re.search(reg_pattern,"".join(sorted(d)))    

if match:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

summary_d = {}
summary_t = {}

for i in range(0, len(d)):
    summary_d[d[i]] = summary_d.get(d[i],0) + 1

for i in range(0, len(t)):
    summary_t[t[i]] = summary_t.get(t[i],0) + 1

result = {}

for k,v in summary_t.items():
    result[k] = summary_d.get(k,0) - v

if min(result.values()) >= 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
a=[]
b=[]
for i in range(n):
  for j in range(i+1,n):
    d=s[i]+s[j]
    if d in b:continue
    else:b.append(d)
    for k in range(j+1,n):
      c=s[i]+s[j]+s[k]
      if c not in a:
        a.append(c)
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for m in range(1000):
  m=str(m).zfill(3)
  j=0
  for i in m:
    if i not in s[j:]:break
    j+=s[j:].index(i)+1
  else:cnt+=1
print(cnt)
### BUGGY CODE ###

W, H, N = map(int, input().split())
X = []
for k in range(N):
  x,y,a = map(int, input().split())
  if a == 1:
    for z in range(1,x+1):
      for j in range(1,H+1):
        X.append([z,j])
  elif a == 2:
    for z in range(x+1,W+1):
      for j in range(1,H+1):
        X.append([z,j])
  elif a == 3:
    for z in range(1,y+1):
      for i in range(1,W+1):
        X.append([i,z])
  else:
    for z in range(y+1,H+1):
      for i in range(1,W+1):
        X.append([i,z])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
print(W*H - len(get_unique_list(X)))

### FIXED CODE ###

W, H, N = map(int, input().split())
X = [0, 0, W, 0, H]
for k in range(N):
  x,y,a = map(int, input().split())
  if a == 1:
    X[a] = max(x,X[a])
  elif a == 2:
    X[a] = min(x,X[a])
  elif a == 3:
    X[a] = max(y,X[a])
  else:
    X[a] = min(y,X[a])
tate = X[4] - X[3]
yoko = X[2] - X[1]
ans = tate*yoko
if tate<0 or yoko<0:
  print(0)
else:
  print(ans)
### BUGGY CODE ###

cnt = 0
def merge(S,left,right,mid):
    a = mid - left
    b = right - mid
    L = [0]*(a+1)
    R = [0]*(b+1)
    for i in range(a):
        L[i] = S[left+i]
    for i in range(b):
        R[i] = S[mid+i]
    L[a] = float("inf")
    R[b] = float("inf")
    j = 0
    k = 0
    for i in range(left,right):
        global cnt
        cnt+=1
        if L[j] <= R[k]:
            S[i] = L[j]
            j += 1
        else:
            S[i] = R[k]
            k += 1
            
def mergeSort(S,left,right):
    if left+1<right:
        mid = (int)((left+right)/2)
        mergeSort(S,left,mid)
        mergeSort(S,mid,right)
        merge(S,left,right,mid)
        
n = int(input())
S = list(map(int, input().split()))
mergeSort(S,0,n)
print(*S)
print(cnt)


### FIXED CODE ###

cnt = 0
def merge(S,left,right,mid):
    a = mid - left
    b = right - mid
    L = S[left:left+a]+[float("inf")]
    R = S[mid:mid+b]+[float("inf")]
    j = 0
    k = 0
    for i in range(left,right):
        global cnt
        cnt+=1
        if L[j] <= R[k]:
            S[i] = L[j]
            j += 1
        else:
            S[i] = R[k]
            k += 1
            
def mergeSort(S,left,right):
    if left+1<right:
        mid = (int)((left+right)/2)
        mergeSort(S,left,mid)
        mergeSort(S,mid,right)
        merge(S,left,right,mid)
        
n = int(input())
S = list(map(int, input().split()))
mergeSort(S,0,n)
print(*S)
print(cnt)
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = np.array([int(input()) for i in range(Q)])
  
points = np.full(N, K) - Q

correct_num = []
for i in range(1, N+1):
  correct_num.append(len(np.where(A==i)[0]))

correct_num = np.array(correct_num)
fin_points = points + correct_num

ans = np.where(fin_points > 0, "Yes", "No")

for i in ans:
  print(i)
  

### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = np.array([int(input()) for i in range(Q)])
  
points = np.full(N, K-Q)

for i in range(0, Q):
  points[A[i]-1] += 1
 
for i in points:
  if i > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

lst=[[] for i in range(N+1)]

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)


### FIXED CODE ###

from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

lst=[[] for i in range(N+1)]

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if p in used:
                used.remove(p)
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)
### BUGGY CODE ###

mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
for j in range(N):
    Ans[0]=Ans[0]*(K)%mod
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        for j in range(N):
            Ans[k-1]=Ans[k-1]*d%mod
        c=d
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7

  
fact_count = [0 for _ in range(K+1)]
for k in range(1, K+1):
  fact_count[k] = K//k

ans = 0
count = [0 for _ in range(K+1)]
for k in range(K, 0, -1):
  c = pow(fact_count[k], N, mod)
  j = 2*k
  l = 2
  while(j<=K):
    c -= count[j]
    l += 1
    j = k*l
  count[k] = c
  c = c*k%mod
  ans += c
  ans %= mod
print(ans)
### BUGGY CODE ###

import sys

INF = float("inf")


def main():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


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

import sys
input = sys.stdin.readline
n,m= map(int,input().split())

B = []
C = [0]*n
ans = 0
pna = 0
for i in range(m):
    A = list(map(str,input().split()))
    if A[0] not in B:
        if A[1]=="AC" :
            B.append(A[0])
            ans += 1
            pna += C[int(A[0])-1]
        else:
      	  C[int(A[0])-1] += 1 
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

import math
N, K = map(int, input().split())

As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
ABs = list(zip(As, Bs, Cs))

def func(target):
    r = 0
    for a, b, c in ABs:
        r += math.ceil(max(0, c - target) / b)
    return int(r <= K)

def bsearch():
    min_i, max_i = 0, max(Cs)+1
    target = 0
    # func(index) <= target < func(index+1) となるindexを返す
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index + 1
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

if __name__ == '__main__':
    print(bsearch())


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

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

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)

### FIXED CODE ###

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

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

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

dist = [float('inf')] * n
def dfs(s, p, depth):
    dist[s] = min(dist[s], depth)
    for to in g[s]:
        if to==p: continue
        if dist[to] < dist[s]+1: continue
        dfs(to, s, depth+1)

dfs(0, -1, 0)

if dist[n-1] <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

dist = [float('inf')] * n
def dfs(s, p, depth):
    if depth>2: return
    dist[s] = min(dist[s], depth)
    for to in g[s]:
        if to==p: continue
        if dist[to] < dist[s]+1: continue
        dfs(to, s, depth+1)

dfs(0, -1, 0)

if dist[n-1] <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

A,B,C,K = map(int, input().split())

for i in range(K):
    a = B+C
    b = A+C
    c = A+B
    A = a
    B = b
    C = c
print(A-B)

### FIXED CODE ###

A,B,C,K = map(int, input().split())

if abs(A-B) > 10**(18):
    print("Unfair")
elif K%2 == 0:print(A-B)
elif K%2 == 1:print(B-A)
### BUGGY CODE ###

import math
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


a=int(input())
i=2
j=1
flag=0
x=0
y=0
min=a**0.5
intmin=int(min)
if not is_prime(a):

    for i in range(intmin,a):
        if a%i == 0:
            if i!=a:
                print(int(i-2+(a/i)))
            else:
                print(a-1)
            break
else:
    print(a-1)



# try:
#     for i in range(2,a//2):
#         mod=a%i
#         if mod==0:
#             if min > (a/i) + i -2:
#                 min = (a/i) + i -2
#     print(min)
# except ZeroDivisionError:
#     print("ZeroDivisionError!!")


### FIXED CODE ###

import math
import copy

n=int(input())

i=int(n**0.5)
j=0
# print(i)

for i in range(i+1,0,-1):
    # print(i)
    if n==i:
        print(n-1)
        break
    if n%i==0:
        j=n/i
        print(int(i+j-2))
        break
### BUGGY CODE ###

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

sum = 0
i = 0

while i < k:
  if i < a:
    sum += 1
    i += 1
  elif i < a + b:
    i += 1
  else:
    sum -= 1
    i += 1

print(sum)

### FIXED CODE ###

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

if k <= a:
  print(k)
elif k <= a + b:
  print(a)
else:
  print(2*a - k + b)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
import numpy as np
A = np.array(A)
for i in range(n):
    b = np.where(A==i+1)
    print(b[0][0]+1)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0]*n
for i in range(n):
  B[A[i]-1] = i + 1 
for i in range(n):
  print(B[i])
### BUGGY CODE ###

l, r = map(int, input().split())
"""
もしl~rの範囲に2019の倍数を含むならば、2019の倍数をi,jのいずれかに設定して0を得る。
それ以外の場合、l~rの範囲は高々2019程度なので、全探索で間に合う
"""
if l//2019 - r//2019 > 0:
    print(0)
else:
    ans = 2019
    for i in range(l, r):
        for j in range(l+1, r+1):
            ans = min(ans, (i*j)%2019)
    print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
"""
もしl~rの範囲に2019の倍数を含むならば、2019の倍数をi,jのいずれかに設定して0を得る。
それ以外の場合、l~rの範囲は高々2019程度なので、全探索で間に合う
"""
if r//2019 - l//2019 > 0:
    print(0)
else:
    ans = 2019
    for i in range(l, r):
        for j in range(l+1, r+1):
            ans = min(ans, (i*j)%2019)
            if ans == 0:
                break
    print(ans)
### BUGGY CODE ###

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if i not in dp:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


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

import itertools
import math

k = int(input())
ans = 0
t = 0
for x, y, z in itertools.product(range(1, k+1), range(1, k+1),range(1, k+1)):
    ans = math.gcd(x, y)
    ans = math.gcd(ans, z)
    t+=ans

print(t)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
t = 0
for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            t += gcd(gcd(i1, i2), i3)
print(t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 8)

MOD = 10 ** 9 + 7

N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

# B = [0] * (N + 1) #自分自身が黒色の時
# W = [0] * (N + 1) #自分自身が白色の時
# T = [0] * (N + 1) #B + W
C = [False] * (N + 1) #訪れたことのチェック

def calc(x): #xからの動き方を調べる
    C[x] = True

    b = 1
    w = 1

    for next_ in G[x]:
        if C[next_]:
            continue
        tmp_b, tmp_w = calc(next_)
        b = (b * tmp_b) % MOD
        w = (w * tmp_w) % MOD
    # B[x] = b
    # W[x] = w
    return w, (b + w) % MOD

tmp, ans = calc(1)
print (ans)
# print ((B[1] + W[1]) % MOD)

### FIXED CODE ###

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

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

    N = int(input())
    G = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        G[x].append(y)
        G[y].append(x)

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #xからの動き方を調べる
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

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

from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   dic[Fraction(A,B)]+=1
ans=1
for k in dic:
 if -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
cs=[None]*m
for i in range(m):
  cs[i]=list(map(int,input().split()))

import heapq
heapq.heapify(a)
for q in cs:
  b=q[0]
  c=q[1]
  for i in range(b):
    v=heapq.heappop(a)
    if v>=c:
      heapq.heappush(a,v)
      break
    else:
      heapq.heappush(a,c)
print(sum(a))

### FIXED CODE ###

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

Q=[None]*M
for i in range(M):
  b,c=map(int,input().split())
  Q[i]=[b,c]
  
Q=sorted(Q,key=lambda x:x[1])[::-1]

A=sorted(A)
ind=0
for i in range(len(Q)):
  b,c=Q[i]
  for p in range(b):
    if ind+p>=len(A):
      print(sum(A))
      exit(0)
    if A[ind+p]<c:
      A[ind+p]=c
    else:
      break
  ind+=b
else:
  print(sum(A))
### BUGGY CODE ###

def main():
    N = int(input().strip())
    A = [int(_a) for _a in input().strip().split()]
    Q = int(input().strip())
    BCS = []
    for i in range(Q):
        BCS.append([int(_bc) for _bc in input().strip().split()])

    Amap = {}
    for a in A:
        if a not in Amap:
            Amap[a] = 0
        Amap[a] += 1


    for bc in BCS:
        b = bc[0]
        c = bc[1]
        if b in Amap:
            num = Amap[b]
            del Amap[b]
        else:
            num = 0

        if c not in Amap:
            Amap[c] = 0
        Amap[c] += num

        total = 0
        for k,v in Amap.items():
            total += (k*v)
        print(total)

main()



### FIXED CODE ###

def main():
    N = int(input().strip())
    A = [int(_a) for _a in input().strip().split()]
    Q = int(input().strip())
    BCS = []
    for i in range(Q):
        BCS.append([int(_bc) for _bc in input().strip().split()])

    Amap = {}
    for a in A:
        if a not in Amap:
            Amap[a] = 0
        Amap[a] += 1

    total = 0
    for k,v in Amap.items():
        total += (k*v)

    for bc in BCS:
        b = bc[0]
        c = bc[1]
        if b in Amap:
            num = Amap[b]

            del Amap[b]
            if c not in Amap:
                Amap[c] = 0
            Amap[c] += num

            total = total + num*c - num*b

        print(total)

main()
### BUGGY CODE ###

from collections import deque
s=input()
s_list=list(s)
length=len(s)
K=int(input())
o=[]
x=deque(sorted(set(s)))



while len(o) < K:
    letter=x.popleft()
    X=[i for i , x in enumerate(s_list) if x==letter]
    for i in X:
        for j in range(i+1,length+1):
            if not s[i:j] in o:
                o.append(s[i:j])




o.sort()
print(o[K-1])


### FIXED CODE ###

from collections import deque
s=input()
s_list=list(s)
length=len(s)
K=int(input())
o=[]
x=deque(sorted(set(s)))

while len(o) < K:
    letter=x.popleft()
    X=[i for i , x in enumerate(s_list) if x==letter]
    for i in X:
        for j in range(i+1,length+1):
            if not s[i:j] in o:
                o.append(s[i:j])
            if j-1-i == 5:
                break

o.sort()
print(o[K-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=[0]*60
for elem in a:
    for i in range(60):
        cnt[i]+=(elem>>i)%2
ans=0
for i in range(60):
    ans+=((cnt[i]*(n-cnt[i]))<<i)%mod
print(ans%mod)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=[0]*60
for elem in a:
    for i in range(60):
        cnt[i]+=(elem>>i)%2
ans=0
for i in range(60):
    ans+=((cnt[i]*(n-cnt[i]))<<i)%mod
print(ans%mod)
### BUGGY CODE ###

N = int(input())
lst = [int(i) for i in input().split()]
while len(lst) > 2:
    lst.remove(min(lst))
    lst.remove(max(lst))
print(max(lst)-min(lst))


### FIXED CODE ###

N = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
x = int(N/2)
print(lst[x]-lst[x-1])
### BUGGY CODE ###

def main():
    n,k=map(int, input().split())
    s=[]
    for _ in range(k):
        l,r=map(int,input().split())
        for j in range(l,r+1):
            s.append(j)
    mod=998244353
    dp=[0]*n
    dp[0]=1
    for i in range(1,n):
        for j in s:
            if i-j>=0:
                dp[i]+=dp[i-j]
                dp[i]%=mod
    print(dp[-1])
main()

### FIXED CODE ###

n,k=map(int, input().split())
lr=[list(map(int,input().split())) for _ in range(k)]
mod=998244353
dp2=[0]*n
dp2[0]=1
for i in range(1,n):
    dp2[i]+=dp2[i-1]
    for l,r in lr:
        if i-l>=0:
            dp2[i]+=dp2[i-l]
        elif i-l<0 and i-r>=0:
            dp2[i]+=dp2[0]
        if i-r-1>=0:
            dp2[i]-=dp2[i-r-1]
    dp2[i]%=mod
print((dp2[-1]-dp2[-2])%mod)