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

s = input()
t = input()

# atoz = [chr(i) for i in range(97,97+26)]


for i in range(len(s)):
    if s[i] == t[i]:
        continue
    else:
        s = s.translate(s.maketrans({s[i]:t[i], t[i]:s[i]}))

if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys

s = input()
t = input()

# atoz = [chr(i) for i in range(97,97+26)]


for i in range(len(s)):
    if s[i] == t[i]:
        continue
    else:
        s_tmp = s
        s = s.translate(s.maketrans({s[i]:t[i], t[i]:s[i]}))
        if s_tmp[:i] != s[:i]:
            print("No")
            sys.exit()
        else:
            pass


if s == t:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

s = input()
l = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] = 1

for i in range(1, l + 1):
    if s[i-1] =="?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)


### FIXED CODE ###

s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
ls = []
for i in range(N):
  if A[A[i]-1] == i+1:
    k = [A[i]-1,i]
    k.sort()
    if k not in ls:
      ls.append(k)
print(len(ls))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
ls = []
for i in range(N):
  if A[A[i]-1] == i+1:
    ans += 1
print(ans//2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i in range(1,n+1):
    ans[i-1]=a.count(i)
print(*ans,sep="\n")



### FIXED CODE ###

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

n = int(input())
*A, = map(int, input().split())
p = 10**9+7
A = [list(format(a, '060b')) for a in A]
s = 0
for i in range(60):
    Ai = [int(a[i]) for a in A]
    c0 = Ai.count(0)
    c1 = Ai.count(1)
    c = c0*c1
    s = (s+c*(2**(59-i))) % p
print(s)


### FIXED CODE ###

N=int(input())
A=[format(i,'060b') for i in map(int,input().split())]
ans=0
mod=10**9+7
for k in range(60):
    count=[a[60-1-k] for a in A].count('0')
    ans+=count*(N-count)*(2**k)%mod
print(ans%mod)
### BUGGY CODE ###

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

def isAsc(lst):
  for i in range(1,len(lst)):
    if lst[i-1]>lst[i]:
      return False
  else:
    return True

answer_list=[]
if max(alist)>0:
  while(not isAsc(alist)):
    desc_index=-1
    desc_diff=0
    
    for i in range(1,N):
      if alist[i-1]>alist[i]:
        desc_index=i
        desc_diff=alist[i-1]-alist[i]
        break
  
    max_a=-10**9
    max_index=-1
    for i in range(N):
      if alist[i]>max_a:
        max_a=alist[i]
        max_index=i    
      
    while(alist[i-1]>alist[i]):
      alist[i]+=max_a
      answer_list.append((max_index+1,i+1))
else:
  while(not isAsc(alist)):
    desc_index=-1
    desc_diff=0
    
    for i in reversed(range(1,N)):
      if alist[i-1]>alist[i]:
        desc_index=i-1
        desc_diff=alist[i-1]-alist[i]
        break
  
    min_a=10**9
    min_index=-1
    for i in range(N):
      if alist[i]<min_a:
        min_a=alist[i]
        min_index=i    
      
    while(alist[i-1]>alist[i]):
      alist[i-1]+=min_a
      answer_list.append((min_index+1,i))

#print(answer_list)
print(len(answer_list))
for x,y in answer_list:
  print(x,y)

### FIXED CODE ###

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

def isAsc(lst):
  for i in range(1,len(lst)):
    if lst[i-1]>lst[i]:
      return False
  else:
    return True

min_a=min(alist)
max_a=max(alist)

answer_list=[]
if max_a>0 and max_a>-min_a:
  while(not isAsc(alist)):
    desc_index=-1
    
    for i in range(1,N):
      if alist[i-1]>alist[i]:
        desc_index=i
        break
  
    max_a=-10**9
    max_index=-1
    for i in range(N):
      if alist[i]>max_a:
        max_a=alist[i]
        max_index=i    
      
    while(alist[desc_index-1]>alist[desc_index]):
      alist[desc_index]+=max_a
      answer_list.append((max_index+1,desc_index+1))
else:
  while(not isAsc(alist)):
    desc_index=-1
    
    for i in reversed(range(1,N)):
      if alist[i-1]>alist[i]:
        desc_index=i-1
        break
  
    min_a=10**9
    min_index=-1
    for i in range(N):
      if alist[i]<min_a:
        min_a=alist[i]
        min_index=i    
      
    while(alist[desc_index]>alist[desc_index+1]):
      alist[desc_index]+=min_a
      answer_list.append((min_index+1,desc_index+1))

#print(answer_list)
print(len(answer_list))
for x,y in answer_list:
  print(x,y)
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

begin = 0
till = K

max = 0
for i in range(N-K+1):
    partial = np.sum(p[begin:till])
    if(max < partial): max = partial
    begin += 1
    till += 1



print((max + K) / 2)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

begin = 0
till = K

max = np.sum(p[0:K])
partial = max
for i in range(N-K):
    partial = partial - p[begin] + p[till]
    if(max < partial):
        max = partial

    begin += 1
    till += 1

print((max + K) / 2)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**5
dp=[INF for i in range(n)]
dp[0]=0
if k>n-1:
    k=n-1
for i in range(1,k+1):
    dp[i]=abs(h[i]-h[0])
for m in range(1,n+1):
    for j in range(1,k+1):
        for i in range(m-j):
            dp[i+j]=min(dp[i]+abs(h[i+j]-h[i]),dp[i+j])
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF for i in range(n)]
dp[0]=0
if k>n-1:
    k=n-1
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            break
        dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
#print(lis)
dp = [[1000] * len(lis) for _ in range(len(lis))]
def dfs(money,kabu,now):
    if now == len(lis):
        return a.append(money)
    if kabu != 0:
        dfs(money + kabu*lis[now],0,now+1)
    if money//lis[now] >= 1:
        dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
a = []

dfs(1000,0,0)

print(max(a))


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
money = 1000
kabu = 0
for i in range(1,n):
    if A[i-1] < A[i]:
        kabu = money // A[i-1]
        money -= kabu * A[i-1]
        money += kabu * A[i]
        kabu = 0
    #print(money,kabu)
print(money)
### BUGGY CODE ###

import math
k=int(input())
a=1
b=1
c=1
s=0
for p in range(k):
  b=1
  for q in range(k):
    c=1
    for i in range(k):
      g=math.gcd(a,b)
      g=math.gcd(g,c)
      s=s+g
      c=c+1
    b=b+1
  a=a+1
print(s)

### FIXED CODE ###

import math
k=int(input())
s=0
for p in range(k):
  for q in range(k):
    g=math.gcd(p+1,q+1)
    for i in range(k):
      r=math.gcd(g,i+1)
      s=s+r
print(s)
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = []
for i in range(n):
    b.append((1+a[i])/2)
    
ans = sum(b[:k])
for i in range(1,n-k+1):
    ans= max(sum(b[i:i+k]), ans)    
print(ans)

### FIXED CODE ###

from itertools import accumulate
n,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = []

num = 0
maxi= 0
l = list(accumulate([0] + a))
for i in range(0,n-k+1):
    if l[i+k] - l[i] > maxi:
        maxi = l[i+k] - l[i]
        num = i  

for i in range(n):
    b.append((1+a[i])/2)
    
ans = sum(b[num:k+num])
print(ans)
### BUGGY CODE ###

from collections import*
n,*s=[t[:-1]for t in open(0)]
s=deque(s)
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s.rotate(1)
print(c)

### FIXED CODE ###

n,*s=[t[:-1]for t in open(0)]
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)
### BUGGY CODE ###

a,b,n=map(int,input().split())
maxf=0
if n>=b:
  for i in range(n//b):
    x=b*(i+1)-1
    if maxf<=(a*x)//b-a*(x//b):
      maxf=(a*x)//b-a*(x//b)
  print(maxf)
else:
  print((a*n)//b-a*(n//b))

### FIXED CODE ###

a,b,n=map(int,input().split())
if n<b:
  print(a*n//b)
else:
  if n==b:
    print(a*(n-1)//b)
  else:
    i=n//b
    print(max((a*n//b-a*i),(a*(b*i-1)//b-a*(i-1))))
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

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

N=int(input())
A=input()
c=0
for i in range(N-2):
 B2=A[i+1]
 for j in range(i+1):
  B1=A[j]
  for k in range(N-i-2):
   B3=A[i+2+k]
   if B1==B2 or B2==B3 or B1==B3 or i==j+k:
    continue
   else:
    c+=1
print(c)


### FIXED CODE ###

N=int(input())
A=input()
c=0
B1B=0
B1R=0
B1G=0
if A[0]=="B":
 B1B+=1
elif A[0]=="R":
 B1R+=1
else:
 B1G+=1
for i in range(N-2):
 B2=A[i+1]
 for k in range(N-i-2):
  B3=A[i+2+k]
  if (B2=="B" and B3=="R")or (B2=="R" and B3=="B"):
   c+=B1G
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="G":
     c-=1
  if (B2=="G" and B3=="R")or (B2=="R" and B3=="G"):
   c+=B1B
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="B":
     c-=1
  if (B2=="B" and B3=="G")or (B2=="G" and B3=="B"):
   c+=B1R
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="R":
     c-=1
 if B2=="B":
  B1B+=1
 elif B2=="R":
  B1R+=1
 else:
  B1G+=1
print(c)
### BUGGY CODE ###

# 入力
num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = []

for w in range(0, weight_limit + 1):
    dp.append([])
    for n in range(0, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if w == 0 or n == 0:
            dp[w].append(0)

        elif weight <= w and value + dp[w - weight][n-1] > dp[w][n-1]:
            dp[w].append(value + dp[w - weight][n-1])

        else:
            dp[w].append(dp[w][n-1])

print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = np.zeros(weight_limit + 1)

for n in range(num):
    w = wv_list[n][0]
    v = wv_list[n][1]
    dp[w:] = np.maximum(dp[:-w] + v, dp[w:])

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

# coding: utf-8
# Your code here!
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
l ={}
N,K = map(int,input().split())
P = list(map(int,input().split()))
P_ = []

def kitai(num):
    x = 0
    for j in range(num):
        x += num-j
    return x/num
for i in P:
    P_.append(kitai(i))
#print(P_)


#print(P)
for i in range(0,N-K+1):
    #print(P[i:i+K])
    l[sum(P_[i:i+K])]=i
#print(l)
max = max(l.keys())
print(max)








### FIXED CODE ###

#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

N,K = map(int,input().split())
def kitai(num):
    return (1+int(num))/2
P = list(map(kitai,input().split()))	  

S = [0]*(N+1)
ans = 0
for i in range(N):
    S[i+1]=S[i]+P[i]
for i in range(N-K+1):
    ans = max(ans,S[i+K]-S[i])
print(ans)
### BUGGY CODE ###

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


k = int(input())

ans = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        for n in range(1, k + 1):
            ans += gcd(gcd(i, j), n)

print(ans)


### FIXED CODE ###

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

k = int(input())
res = [0] * (k + 1)

ans = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        res[gcd(i, j)] += 1

for n in range(1, k + 1):
    for r in range(1, k + 1):
        ans += gcd(r, n) * res[r]

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

import math
num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    j = 0
    k = 0
    l = 0
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j > k:
                        if k > l:
                            xyz_count += 6
                        else:
                            xyz_count += 3
                    elif k == l:
                        xyz_count += 1
                    else:
                        xyz_count += 3
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

N, K = map(int, raw_input().split())

h = list(map(int, raw_input().split()))
dp = [10 ** 9 + 1] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, i + K + 1):
        if j < N:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
        else:
            break
print(dp[N - 1])

### FIXED CODE ###

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

h = list(map(int, input().split()))
dp = [10 ** 9 + 1] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, i + K + 1):
        if j < N:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
        else:
            break
print(dp[N - 1])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

           
for i in range(0,len(a)):
  ax = a.copy()
  del a[i]
  print(max(a))
  a = ax.copy()
  

  #  if 1+i<=len(a):
#    print('i:' ,i)
#    print(max(a[i],a[i+1]))

        
#print(max(a[0],a[-1]   )   )  

### FIXED CODE ###

n = int(input())
a = []
x = 0
x_max = 0
for _ in range(n):
  x = int(input())
#  if x_max 
  a.append(x)

b = a.copy()  
b.sort(reverse=True)
a_max1 = b[0]
a_max2 = b[1] 

for i in a:
  if i == a_max1:
    print(a_max2)
  else:
    print(a_max1)
### BUGGY CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
front=[]
back=[]
for i in range(n//2):
    front.insert(0, a[2*i-(n%2)+1])
    back.append(a[2*i+(n%2)])
if n%2==1:
    front.insert(0, a[n-1])
print(' '.join(map(str, front+back)))

### FIXED CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
flg=n%2
half=n//2
front=[0]*(half+flg)
back=[0]*(half)
for i in range(half):
    front[half+flg-1-i]=a[2*i-flg+1]
    back[i]=a[2*i+flg]
if flg==1:
    front[0]=a[n-1]
print(' '.join(map(str, front+back)))
### BUGGY CODE ###

import numpy as np
N = int(input())
lst = list(map(int, input().split()))

s = np.zeros((N, N))
d = np.zeros((N, N))

for i in range(N):
    for j in range(i+1, N):
        s[i, j] += lst[i] + lst[j]
        d[i, j] += abs(lst[i] - lst[j])


res = 0
for k in range(N):
    val = lst[k]
    slow = s>val
    dhigh = d<val
    sandd = slow & dhigh
    
    sandd[k, :] = False
    sandd[:, k] = False
    
    res += np.count_nonzero(sandd)
print(res//3)

### FIXED CODE ###

### a<=b<=cととることとし、a,bを固定すると
### cは　c<a+b
N = int(input())
lst = list(map(int, input().split()))
sor = sorted(lst)

def BinarySearch(lst, key): ## lstの値のうち、key以上になる最初のインデックス
    left = -1  ## index=0が条件を満たす場合も存在
    right = len(lst)  ## index = len(lst)-1が条件を満たさないこともある、key以上になるものが存在しない
    
    while right != left + 1:
        mid = (left + right) // 2
        val = lst[mid]
        if val >= key:
            right = mid
        elif val < key:
            left = mid
    return right  ### key以上になるものが存在しない場合はlen(lst)が帰る

res = 0
for i in range(N):
    for j in range(i+1, N):##ここでa<=bを満たしている
        a = sor[i]
        b = sor[j]
        ab = a+b

        highbound = BinarySearch(sor, ab)
        res += highbound - j - 1
print(res)
### BUGGY CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]

for i in range(n):
  s[i].sort()

count=0
for i in range(n-1):
  for j in range(i+1,n):
    if s[i]==s[j]:
      count+=1
      
print(count)


### FIXED CODE ###

n=int(input())
s=[''.join(sorted(list(input()))) for _ in range(n)]
s.sort()
t=list(sorted(set(s)))

count=[1]*len(t)
j=0
for i in range(1,n):
  if t[j]==s[i]:
    count[j]+=1
  else:
    j+=1

ans=0
for i in range(len(t)):
  ans+=((count[i])*(count[i]-1))//2
  
print(ans)
### BUGGY CODE ###

n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
a=sorted(a)
diff=[]
for i in range(m):
    b,c=[int(x) for x in input().split()]
    diff+=[c]*b
diff=sorted(diff,reverse=True)
diff+=[0]*n
# print(a)
# print(diff)
ans=[]
for i in range(n):
    ans.append(max(a[i],diff[i]))
print(sum(ans))

### FIXED CODE ###

n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
a=sorted(a)
diff=[]
bc=[]
for i in range(m):
    b,c=[int(x) for x in input().split()]
    bc.append((b,c))
bc=sorted(bc,key=lambda x : x[1],reverse=True)
# print(bc)
for b,c in bc:
    if len(diff)<=n:
        diff+=[c]*b
diff+=[0]*(n-len(diff))
# print(a)
# print(diff)
ans=[]
for i in range(n):
    ans.append(max(a[i],diff[i]))
print(sum(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
count = 0
for i in range(N):
    count += 1
    th_list.append(n)
#   print(n)
    n = city_list[n] - 1
''' if n in th_list:
        #繰り返されている個数を出す
        num = len(th_list)-th_list.index(n)
        break'''

#print(city_list, th_list)
count = -1
for i in range(N):
    if th_list.count(th_list[i]) > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]
#print(list)
#print(list[0])
#print(th_list)
if K > N:
    print(th_list[(K-list[0])%(list[1]-list[0])+list[0]]+1)
else:
    print(th_list[K]+1)

### FIXED CODE ###

import collections

N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
for i in range(N):
    th_list.append(n)
    n = city_list[n] - 1

c = collections.Counter(th_list)
for i in range(N):
    if c[th_list[i]] > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]

if K > N:
    print(th_list[(K - list[0]) % (list[1] - list[0]) + list[0]] + 1)
else:
    print(th_list[K] + 1)
### BUGGY CODE ###

s = input()
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            R += a[2]
        else:
            F = a[2] + F
ans = F + s + R
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

from collections import deque
d = deque()
d.extend(list(input()))
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = tuple(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            d.append(a[2])
        else:
            d.appendleft(a[2])

ans = "".join(d)
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

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

price_list = [int(i) for i in price_list]
 
for m in range(M):
  max_num = price_list.index(max(price_list))
  price_list[max_num] = int(price_list[max_num] / 2)
print(sum(price_list))

### FIXED CODE ###

import heapq

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
heap_list = []
for i in price_list:
  heapq.heappush(heap_list, int(i) * (-1))

for _ in range(M):
  max_num = heapq.heappop(heap_list)
  heapq.heappush(heap_list, int(max_num /2))
  
print(sum(heap_list) * (-1))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ls, rs = [], []
for _ in range(Q):
    l, r = map(int, input().split())
    ls.append(l-1)
    rs.append(r-1)

indices = []
flag = False
for i in range(len(S)):
    if S[i] == 'A':
        flag = True
    elif S[i] == 'C' and flag:
        indices.append(i - 1)
    else:
        flag = False

for l, r in zip(ls, rs):
    print(len(list(filter(lambda idx: idx in range(l, r), indices))))


### FIXED CODE ###

import numpy as np

N, Q = map(int, input().split())
S = input()
ls, rs = [], []
for _ in range(Q):
    l, r = input().split()
    ls.append(int(l)-1)
    rs.append(int(r)-1)

arr = np.zeros(N, np.int)
# flag = False
# for i in range(N):
#     if S[i] == 'A':
#         flag = True
#     elif S[i] == 'C' and flag:
#         arr[i - 1] = 1
#     else:
#         flag = False
for i, (a, c) in enumerate(zip(S, S[1:])):
    if a == 'A' and c == 'C':
        arr[i] = 1

cum = np.cumsum(arr)

for l, r in zip(ls, rs):
    if l == 0:
        print(cum[r-1])
    else:
        print(cum[r-1] - cum[l-1])