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

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += (ql * 3**max(0, ql-1) + a * 3**ql) * (qr * 3**max(0, qr-1) + c * 3**qr)
        ans %= 10**9 + 7

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)


### FIXED CODE ###

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
ans=[0]*(10**5+1)
for i in a:
    ans[i]+=1

for i in range(q):
    x=0
    b,c=map(int,input().split())
    ans[c]+=ans[b]
    ans[b]=0
    for j in range(10**5+1):
        if ans[j]==0:
            continue
        x+=(ans[j])*j
    print(x)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = [0] * (100001)
s = sum(A)
for a in A:
    L[a] += 1
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    L[C] += L[B]
    s += L[B] * (C-B)
    L[B] = 0
    print(s)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
Fs = list(map(int, input().split()))
As.sort()
Fs.sort(reverse=True)
def check(x):
  k = 0
  for i in range(N):
    k += max(0, As[i]-x//Fs[i])
  return k <= K
a = 0
b = As[-1]*Fs[0]
while a < b:
  i = (a + b)//2
  if check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
Fs = list(map(int, input().split()))
As.sort()
Fs.sort(reverse=True)
def check(x):
  k = 0
  for i in range(N):
    k += max(0, As[i]-x//Fs[i])
  return k <= K
a = 0
b = As[-1]*Fs[0]
while a < b:
  i = (a + b)//2
  if check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b
print(r)
### BUGGY CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read

H,W,M = list(map(int, input().split()))

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
for i in np.where(h==h.max())[0]:
    for j in np.where(w==w.max())[0]:
        mxh_v = h[i]
        mxw_v = w[j]

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            break

print(a)

### FIXED CODE ###

H,W,M = list(map(int, input().split()))

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
### BUGGY CODE ###

N, W = map(int, input().split())
#WV = [list(map(int, input().split())) for i in range(N)]
DP = [[0] * (W+1) for i in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  for w in range(1,W+1):
    if w >= wn:
      DP[n][w] = max(DP[n-1][w-wn] + vn, DP[n-1][w])
    else:
      DP[n][w] = DP[n-1][w]
print(DP[N][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
max = 0.0
for i in range(n-k+1):
  sum = 0
  for j in range(k):
    d = a[i+j]
    sum += (((d+1)*d)/2)/d
  if max < sum:
    max = sum
print(max)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = {}
r = s = m = 0
for i in range(k):
  s += a[i]
  if a[i] in b:
    pass
  else:
    d = a[i]
    b[d] = (d+1)/2.0
m = s
    
for i in range(n-k):
  s = s - a[i] + a[k+i]
  if a[k+i] in b:
    pass
  else:
    d = a[k+i]
    b[d] = (d+1)/2.0
  if m < s:
    m = s
    r = i+1
    
sp = 0.0
for i in range(k):
  sp += b[a[r+i]]
print(sp)
### BUGGY CODE ###

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


def is_anaglam(a, b):
  if sorted(list(a)) == sorted(list(b)):
    return True
  return False


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

### FIXED CODE ###

def sort_str(str):
  return ''.join(sorted(list(str)))

n = int(input().rstrip())
s = [sort_str(input().rstrip()) for _ in range(n)]

ans = 0
pool = {}
for i in range(n):
  if not s[i] in pool.keys():
    pool[s[i]] = 0
  else:
    pool[s[i]] += 1
    ans += pool[s[i]]
print(ans)
### BUGGY CODE ###

n = int(input())
    
def f(x, result):
    if x == 1:
        return 1
    while True:
        if x % 2 == 0:
            qcnt = 0
            while True:
                x = x // 2
                qcnt += 1
                if x % 2 != 0:
                    break
            return result[x] * (qcnt + 1)
        else:
            break
    
    while True:
        if x == 1:
            break
        else:
            p = 3
            while True:
                if x % p == 0:
                    pcnt = 0
                    while True:
                        x = x // p
                        pcnt += 1
                        if x % p != 0:
                            break
                    return result[x] * (pcnt + 1)
                else:
                    p += 2
    y = 1
    for i in yakusu.values():
        y *= (i+1)
    return y
    

s = 0
result = {1:1}
for i in range(1,n+1):
    result[i] = f(i, result)
    s += i * f(i,result)
    

print(s)

### FIXED CODE ###


n = int(input())
s = 0
for i in range(1,n+1):
    s +=  i * ( (n // i) * (n // i + 1) // 2 )


print(s)
### BUGGY CODE ###

a = [[0]*3005 for _ in range(3005)]
dp = [[[0]*4 for _ in range(3005)] for _ in range(3005)]
R, C, K = map(int, input().split())
for i in range(K):
    r, c, v = map(int, input().split())
    a[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+a[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])

ans = 0
for i in range(4):
    ans = max(ans, dp[R-1][C-1][i])
print(ans)

### FIXED CODE ###

r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)
### BUGGY CODE ###

from collections import defaultdict

n, l = map(int, input().split())
nums = defaultdict(set)
for s in (input() for _ in range(n)):
    nums[l - len(s) + 1].add(int(s, 2) + (1 << len(s)))

xor = 0
for i in range(min(nums), l + 1):
    ni = nums[i]
    for k in ni:
        if k ^ 1 not in ni:
            xor ^= i & -i
        nums[i + 1].add(k // 2)
    del nums[i]

print('Alice' if xor else 'Bob')


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)


def dfs(cur, dep=0):
    if cur == -1:
        x = l - dep
        return x & -x
    return dfs(trie[cur][0], dep + 1) ^ dfs(trie[cur][1], dep + 1)


n, l = map(int, input().split())
trie = [[-1, -1] for _ in range(100001)]
idx = 1
for s in (input() for _ in range(n)):
    cur = 0
    for c in map(int, s):
        if trie[cur][c] == -1:
            trie[cur][c] = idx
            idx += 1
        cur = trie[cur][c]

xor = dfs(trie[0][0]) ^ dfs(trie[0][1])
print('Alice' if xor else 'Bob')
### BUGGY CODE ###

n = int(input())

num_div = 10**9 +7
power = 1
for i in range(1,n+1):
    power = power*i
#     print(power, power%num_div)
print(power%num_div)

### FIXED CODE ###

n = int(input())

num_div = 10**9 +7
remainder_power = 1
for i in range(1,n+1):
    remainder_power = (remainder_power*i)%num_div
print(remainder_power)
### BUGGY CODE ###

N,K = map(int, input().split())
PList = list(map(int, input().split()))
CList = list(map(int, input().split()))
for i in range(N):
  PList[i] -= 1

ans = -1*(10**18)
for si in range(N):
  x = si
  s = list()
  total = 0
  while(1):
    x = PList[x]
    s.append(CList[x])
    total += CList[x]
    if x == si:
      break
  l = len(s)
  t = 0
  for i in range(l):
    t += s[i]
    if i+1 > K:
      break
    now = t
    if total > 0:
      e = (K-i-1)//l
      now += total*e
    ans = max(ans, now)  
print(ans)
    

### FIXED CODE ###

N,K = map(int, input().split())
PList = list(map(int, input().split()))
CList = list(map(int, input().split()))

ans = -1*(10**18)
for si in range(N):
  x = si
  s = list()
  total = 0
  l = 0
  while(1):
    x = PList[x]-1
    s.append(CList[x])
    l += 1
    total += CList[x]
    if x == si:
      break
  t = 0
  for i in range(l):
    t += s[i]
    if i+1 > K:
      break
    now = t
    if total > 0:
      e = (K-i-1)//l
      now += total*e
    ans = max(ans, now)  
print(ans)
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

import copy

n,m = map(int,input().split()) #n:頂点数　w:辺の数
l=[list(map(int,input().split())) for i in range(m)]
ans=0

#d[u][v] : 辺uvのコスト(存在しないときはinf)
for j in range(m):
	d = [[float("inf") for i in range(n)] for i in range(n)]
	b=l[:j]+l[j+1:]
	for i in range(m-1):
		x,y = b[i][0],b[i][1]
		x-=1;y-=1
		d[x][y] = 1
		d[y][x] = 1
	for i in range(n):
		d[i][i] = 0 #自身のところに行くコストは０
	for i in range(n):
		for k in range(n):
			if warshall_floyd(d)[i][k]==float("inf"):
				ans+=1
				break
		else:
			continue
		break
	b=copy.deepcopy(l)
print(ans)

### FIXED CODE ###

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,w = map(int,input().split())
l=[list(map(int,input().split())) for i in range(w)]
ans=0
#edge[i] : iから出る道の[重み,行先]の配列
for j in range(w):
    edge = [[] for i in range(n)]
    b=l[:j]+l[j+1:]
    for i in range(w-1):
        x,y = b[i][0],b[i][1]
        x-=1;y-=1
        z=1
        edge[x].append([z,y]) #有向辺
        edge[y].append([z,x]) #有向辺
    if float("inf") in dijkstra_heap(0):
            ans+=1
print(ans)
### BUGGY CODE ###

(k,s),c=map(int,input().split()),0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:c+=1
print(c)

### FIXED CODE ###

(k,s),c=map(int,input().split()),0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:c+=1
print(c)
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = {}
for i in range(K):
	r, c, v = rl()
	I[(r, c)] = v

dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[ni][nj][m] = max(dp[ni][nj][m], dp[i][j][m])
			if m < 3 and (ni,nj) in I:
				dp[ni][nj][m+1] = max(dp[ni][nj][m+1], dp[i][j][m]+I[(ni,nj)])

			ni, nj = i+1, j
			dp[ni][nj][0] = max(dp[ni][nj][0], dp[i][j][m])
			if (ni, nj) in I:
				dp[ni][nj][1] = max(dp[ni][nj][1], dp[i][j][m]+I[(ni,nj)])
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)
### BUGGY CODE ###

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

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

L_gcd = [A[0]]
R_gcd = [A[-1]]

for i in range(1,N):
    L_gcd.append(gcd(L_gcd[i-1],A[i]))
    R_gcd.insert(0,gcd(A[N-i-1],R_gcd[0]))

ans = max(L_gcd[-2],R_gcd[1])

for i in range(N-2):
    if max(L_gcd[i],R_gcd[i+2])<=ans:
        break
    if gcd(L_gcd[i],R_gcd[i+2])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+2])
print(ans)

### FIXED CODE ###

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

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

L_gcd = [0]*(N+1)
R_gcd = [0]*(N+1)

for i in range(N):
    L_gcd[i+1] = gcd(L_gcd[i],A[i])
    R_gcd[N-i-1] = gcd(R_gcd[N-i],A[N-i-1])

ans = 0
for i in range(N):
    if gcd(L_gcd[i],R_gcd[i+1])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+1])
    
print(ans)
### BUGGY CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1




    def make_divisors(n):
        lower_divisors , upper_divisors = deque(),deque()
        for i in range(1,int(n**0.5)+1):
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.appendleft(n//i)
            i += 1
        upper_divisors
        return lower_divisors + upper_divisors




    F = deque()
    for a in A:
        F.append(make_divisors(a))
    ans = 0
    Not_Divisible = [False] * (max(A)+1)
    for f in F:
        for d in f:
            if Not_Divisible[d]:
                break
        else:
            num = f.pop()
            Not_Divisible[num] = True
            if count[num] == 1:
                ans += 1
    print(ans)

    
main()

### FIXED CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    A = list(set(A))
    A.sort()

    if count[1] == 1:
        print(1)
        return
    if count[1] > 1:
        print(0)
        return

    sup = max(A)+1
    Not_Divisible = [True] * sup
    Not_Divisible[0] = False


    for a in A:
        if Not_Divisible[a]:
            for i in range(a*2,sup,a):
                Not_Divisible[i] = False

    ans = 0
    for a in A:
        if Not_Divisible[a] and count[a] == 1:
            ans += 1

    print(ans)
            


    
main()
### BUGGY CODE ###

A,B,N = map(int,input().split())
def floor(x):
  return int(x//1)
list = []
if N >= B:
  for x in range(B+1):
    list.append(floor((A*x)/B)-(A*floor(x/B)))
else:
    list.append(floor((A*N)/B)-(A*floor(N/B)))
print(max(list))


### FIXED CODE ###

A,B,N = map(int,input().split())
def floor(x):
  return int(x//1)
list = []
if N >= B:
    list.append(floor((A*(B-1))/B)-(A*floor((B-1)/B)))
else:
    list.append(floor((A*N)/B)-(A*floor(N/B)))
print(max(list))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [[2000 for _ in range(W)] for _ in range(H)]
B = []
for h in range(H):
    a = input()
    if a.count("#") > 0:
        for w, e in enumerate(a):
            if e == "#":
                B.append((h, w))
                A[h][w] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for b in B:
    stack = deque()
    stack.append(b)
    while stack:
        x, y = stack.pop()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if -1 < nx < H and -1 < ny < W:
                if A[x][y] + 1 < A[nx][ny]:
                    A[nx][ny] = A[x][y] + 1
                    stack.append((nx, ny))
print(max(max(a) for a in A))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))
### BUGGY CODE ###

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

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

B = []
for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        B.append(c)

A.sort()
B.sort(reverse=True)
for i in range(min(N, len(B))):
    if A[i] < B[i]:
        A[i] = B[i]

ans = sum(A)
print(ans)

### FIXED CODE ###

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

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

count = 0
BC = []
for i in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))

A.sort()
BC.sort(reverse=True, key=lambda x: x[1])

count = 0
CArr = []
for b, c in BC:
    if count >= N:
        break
    for i in range(b):
        CArr.append(c)
        count += 1
        if count >= N:
            break

for i in range(len(CArr)):
    if A[i] < CArr[i]:
        A[i] = CArr[i]

ans = sum(A)
print(ans)
### BUGGY CODE ###

ans=0
flag=1
s=input()
while ans!=flag:
	flag=ans
	ans+=len(s)-len(s.replace("01",""))
	s=s.replace("01","")
	ans+=len(s)-len(s.replace("10",""))
	s=s.replace("10","")
print(ans)

### FIXED CODE ###

s=input()
sum1=len([i for i in s if i=="1"])
sum0=len([i for i in s if i=="0"])
if sum1>sum0:
	print(sum0*2)
else:
	print(sum1*2)
### BUGGY CODE ###

S=input()
ans=0
moku='W'*S.count('W')+'B'*S.count('B')

while S != moku:
    S=S.replace('BW', 'WB', 1)
    ans+=1

print(ans)

### FIXED CODE ###

S=input()
ans=0
cnt=0
for i, s in enumerate(S):
    if s=='W':
        cnt+=1
        ans+=i-cnt+1

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

import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
ln = len(s)
flag = False
for l in range(ln//2)[::-1]:
    d = {}
    for i in range(ln - l):
        c = s[i:i+l+1]
        if c not in d.keys():
            d[c] = i
        else:
            ll = len(c)
            if i >= d[c] + ll:
                print(ll)
                flag = True
                break
    if flag:
        break
if flag is False:
    print(0)





### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

dicts = [{} for _ in range(N)]
for i in range(N):
    for j in range(10):
        c = S[i][j]
        dicts[i][c] = dicts[i].get(c, 0) + 1

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if dicts[i] == dicts[j]:
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
history = {}
ans = 0

for i in range(N):
    sorted_s = ''.join(sorted(S[i]))
    num = history.get(sorted_s, 0)
    ans += num
    history[sorted_s] = num + 1

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

# -*- coding: utf-8 -*-

n = int(input())
l = list(map(int,input().split()))
cnt = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i] < l[j] + l[k] and l[j] < l[k] + l[i] and l[k] < l[i] + l[j]:
                cnt += 1

print(cnt)



### FIXED CODE ###

n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lp = j+1
        rp = n-1
        while lp < rp:
            mp = (lp+rp)//2
            if l[mp] < l[i] + l[j]:
                lp = mp+1
            else:
                rp = mp-1
        if l[lp] < l[i] + l[j]:
            ans += lp-j
        else:
            ans += lp-j-1
print(ans)