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

import functools
import operator


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

ans=functools.reduce(operator.mul, a)

if ans>10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans=1

if 0 in a:
    print(0)
    exit()

for i in a:
   ans*=i
   if ans>10**18:
    print(-1)
    exit()


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

n, k = map(int, input().split())
p = list(map(int, input().split()))

l = tuple(map(lambda x: x * (x + 1) * 1 / 2 * 1 / x, p))

ans = [0] * (n - k + 1)
for i in range(n - k + 1):
    ans[i] = sum(l[i:i + k])

print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

p = list(map(lambda x: x * (x+1) /2 /x, p))

for i in range(1, n):
    p[i] = p[i-1] + p[i]

m = p[k-1]
for i in range(k, n):
    a = p[i] - p[i-k]
    if m < a:
        m = a

print(m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

N,X=map(int,input().split())
x=list(map(int,input().split()))+[X]

from fractions import gcd

x=[abs(x[i+1]-x[i]) for i in range(N)]

def gcd_many(_list):
    if len(_list)==1:
        return abs(_list[0])
    elif len(_list)==2:
        return gcd(_list[0],_list[1])
    else:
        return gcd(_list[0],gcd_many(_list[1:]))
        
print(abs(gcd_many(x)))

### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))+[X]

from fractions import gcd

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

ans=0
for i in range(N):
    ans=gcd(ans,x[i])
print(abs(ans))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans=0
k=int(input())
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans=0
k=int(input())
for a in range(1,k+1):
    for b in range(a+1,k+1):
        for c in range(b+1,k+1):
            ans+=gcd(a,b,c)*6
for a in range(1,k+1):
        for c in range(a+1,k+1):
            b=a
            ans+=gcd(a,b,c)*3
for a in range(1,k+1):
        for c in range(a+1,k+1):
            b=c
            ans+=gcd(a,b,c)*3
print(ans+sum([i for i in range(1,k+1)]))
### BUGGY CODE ###

n = int(input())

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

ans = 1

for i in l:
    ans *= i

if ans > 10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

n = int(input())
 
l = list(map(int,input().split()))
 
if 0 in l:
    print(0)
    exit()
    
ans = 1
 
for i in l:
    ans *= i
    
    if ans > 10**18:
        print(-1)
        exit()

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

import collections

n = int(input())
L = sorted(map(int,input().split()))
ans = []
for i in range(n):
  for j in range(i+1,n):
    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]:
        A = [i,j,k]
        A.sort()
        s = ''.join([str(n) for n in A])
        ans.append(s)
cnt = set(ans)  
print(len(cnt))

### FIXED CODE ###

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

for i in range(N-1,0,-1):
    l = 0
    r = i -1
    while(l< r):
        if (A[l] + A[r] >A[i]):
            count += (r-l)
            r -= 1
        else:
            l += 1
print(count)
### BUGGY CODE ###

import copy

n, t = map(int, input().split())
L = [int(i) for i in input().split()]
LL = copy.deepcopy(L)
LL.sort()

minvalue = L[0]
maxvalue = LL[-1]
subt = 0
count = 1
flag = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  LL.remove(L[i])    
  if maxvalue == L[i]:
    maxvalue = LL[-1]
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
#  print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))

print(count)

### FIXED CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)
### BUGGY CODE ###

N = int(input())
prod = 1
for j in range(1, N+1):
	prod *= j
print(prod%int(1e9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%int(1e9+7))
### BUGGY CODE ###

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

pt = []
G = [0 for x in range(N+1)]
C = [1 for x in range(N+1)]

def find(x):
    while G[x] != 0:
        x = G[x]
    return x

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(C[wx] * C[wy])
        C[wx] += C[wy]
        G[wy] = wx

    #print(G)

cnt = 0
while len(pt):
    cnt += pt.pop()
    print(cnt)


### FIXED CODE ###

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)
### BUGGY CODE ###

# coding: utf-8
X = input()
tmp = ""
for x in X:
    tmp += x
    tmp = tmp.replace("ST","")
print(len(tmp))

### FIXED CODE ###

# coding: utf-8
X = input()
tmp = " "
cnt = 0
for x in X:
    if x == "S":
        tmp += x
        cnt += 1
    elif x == "T" and tmp[-1]=="S":
            cnt -= 1
            tmp = tmp[0:len(tmp)-1]
    else:
        tmp += x
        cnt += 1
print(cnt)
### BUGGY CODE ###

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue(H * W)
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

import sys
input = sys.stdin.readline

from fractions import gcd


MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

setF = set(F)

keys = [k for k in setF]
inv_keys = [(-y,x) for x,y in setF]

all_keys = set()
temp = set(keys) | set(inv_keys)
for x,y in temp:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
all_keys = list(all_keys)


all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
x,y,z,K=map(int,input().split())
listsa=list(map(int,input().split()))#長さはｘ
listsb=list(map(int,input().split()))#長さはy
listsc=list(map(int,input().split()))#長さはz
if x*y>3000:
    suballlist=[]
    for i in listsa:
        for j in listsb:
            suballlist.append(i+j)
    suballlist=sorted(suballlist,reverse=True)
    uselist=suballlist[:3000]
    alllist=[]
    
    for i in uselist:
        for j in listsc:
            alllist.append(i+j)
            
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
    
elif x*y<=3000:
    alllist=[]
    for i in listsa:
        for j in listsb:
            for k in listsc:
                alllist.append(i+j+k)
                
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
x,y,z,K=map(int,input().split())
listsa=list(map(int,input().split()))#長さはｘ
listsb=list(map(int,input().split()))#長さはy
listsc=list(map(int,input().split()))#長さはz
if x*y>3000:
    suballlist=[]
    for i in listsa:
        for j in listsb:
            suballlist.append(i+j)
    suballlist=sorted(suballlist,reverse=True)
    uselist=suballlist[:3000]
    alllist=[]
    
    for i in uselist:
        for j in listsc:
            alllist.append(i+j)
            
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
    
elif x*y<=3000:
    alllist=[]
    for i in listsa:
        for j in listsb:
            for k in listsc:
                alllist.append(i+j+k)
                
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
### BUGGY CODE ###

S=input();T=input()
q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    sc=S[a-1:b].count("A")
    sa=sc-(b-a+1-sc)
    tc=T[c-1:d].count("A")
    ta=tc-(d-c+1-tc)
    if sa%3==ta%3:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

S=input();T=input()
dps=[0]*len(S)
for i in range(len(S)):
    if S[i]=="A":
        dps[i]+=1
    if i!=0:
        dps[i]+=dps[i-1]

dpt=[0]*len(T)
for i in range(len(T)):
    if T[i]=="A":
        dpt[i]+=1
    if i!=0:
        dpt[i]+=dpt[i-1]
dps=[0]+dps
dpt=[0]+dpt

q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    sc=dps[b]-dps[a-1]
    sa=sc-(b-a+1-sc)
    tc=dpt[d]-dpt[c-1]
    ta=tc-(d-c+1-tc)
    if sa%3==ta%3:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

import fractions
import itertools
k = int(input())

ans=k*(k+1)//2
l = [int(i) for i in range(1,k+1)]
for i in itertools.combinations(l,3):
    ans += fractions.gcd(fractions.gcd(i[0],i[1]),i[2])*6

for i in itertools.combinations(l,2):
    ans += fractions.gcd(i[0],i[1])*6

print(ans)

### FIXED CODE ###

import fractions
import itertools
k = int(input())

ans=k*(k+1)//2
for a in range(1,k+1):
    for b in range(a+1,k+1):
        t = fractions.gcd(a,b)
        for c in range(b,k+1):
            ans+=fractions.gcd(t,c)*6

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

import math
N = int(input())
L = list(map(int,input().split()))
B = []
s = 0
for i in range(N-2):
    for k in range(i+1,N-1):
        for _ in range(k+1,N):
            if L[i]-L[k]<L[_] and L[k]-L[i]<L[_] and L[_]<L[i]+L[k]:
                s = (L[i]+L[k]+L[_])/2
                B.append(math.sqrt(s*(s-L[i])*(s-L[k])*(s-L[_])))
k = set(B)
k = list(k)
print(len(k))


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
sum = 0
for i in range(0,N):
  L_1st= L[i]
  for j in range(i+1,N):
    L_2nd = L[j]
    c_min = L_2nd-L_1st+1
    c_max = L_2nd+L_1st-1
    l = bisect.bisect_left(L,c_min,lo = j+1)
    if l!= N:
      r = bisect.bisect_right(L,c_max,lo = j+1)
      if r:
        r = r-1
        if r>= l:
          sum += r-l+1
print(sum)
### BUGGY CODE ###

N = int(input())
MOD_NUM = 10**9 + 7
ans = 1
for i in range(1,N+1):
  ans *= i
print(ans%MOD_NUM)

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9 + 7))
### BUGGY CODE ###

n = int(input())
s = input()

acc_r, acc_g, acc_b = [], [], []
cr, cg, cb = 0, 0, 0
for i in s:
    if i == "R":
        cr += 1
    elif i == "G":
        cg += 1
    elif i == "B":
        cb += 1

    acc_r.append(cr)
    acc_g.append(cg)
    acc_b.append(cb)

count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        si = s[i]
        sj = s[j]
        if (si == "R" and sj == "G") or (si == "G" and sj == "R"):
            count += acc_b[-1] - acc_b[j]
            if j+(j-i) < n and s[j+(j-i)] == "B":
                count -= 1
        if (si == "G" and sj == "B") or (si == "B" and sj == "G"):
            count += acc_r[-1] - acc_r[j]
            if j+(j-i) < n and s[j+(j-i)] == "R":
                count -= 1
        if (si == "R" and sj == "B") or (si == "B" and sj == "R"):
            count += acc_g[-1] - acc_g[j]
            if j+(j-i) < n and s[j+(j-i)] == "G":
                count -= 1
                
print(count)


### FIXED CODE ###

n = int(input())
s = input()

acc_r, acc_g, acc_b = [], [], []
cr, cg, cb = 0, 0, 0
for i in s:
    if i == "R":
        cr += 1
    elif i == "G":
        cg += 1
    elif i == "B":
        cb += 1

    acc_r.append(cr)
    acc_g.append(cg)
    acc_b.append(cb)

count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        si = s[i]
        sj = s[j]
        if (si == "R" and sj == "G") or (si == "G" and sj == "R"):
            count += acc_b[-1] - acc_b[j]
            if j+(j-i) < n and s[j+(j-i)] == "B":
                count -= 1
        if (si == "G" and sj == "B") or (si == "B" and sj == "G"):
            count += acc_r[-1] - acc_r[j]
            if j+(j-i) < n and s[j+(j-i)] == "R":
                count -= 1
        if (si == "R" and sj == "B") or (si == "B" and sj == "R"):
            count += acc_g[-1] - acc_g[j]
            if j+(j-i) < n and s[j+(j-i)] == "G":
                count -= 1
                
print(count)
### BUGGY CODE ###

K=int(input())
 
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
 
ans=0
 
for a in range(1,K+1):
    for b in range(1,K+1):
        hoge=gcd(a,b)
        for c in range(1,K+1):
            g=gcd(hoge,c)
            ans += g
 
print(ans)

### FIXED CODE ###

K=int(input())

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

ans=0
re=[1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]

if K < 102:
    for a in range(1,K+1):
        for b in range(1,K+1):
            hoge=gcd(a,b)
            for c in range(1,K+1):
                g=gcd(hoge,c)
                ans += g
else:
    ans=re[K-101]



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

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
z,*q=[0]*99*M
v=[[]for _ in q]
for a,b in t:v[a-1]+=b,
for i in v[:M]:
 for j in i:heappush(q,-j)
 z-=heappop(q)
print(z)

### FIXED CODE ###

from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        elif q and q[0]<b:heappushpop(q,b)
print(sum(q))
### BUGGY CODE ###

import math

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1:
        return 1
    if tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

if M == 0:
    print(calc(0,N))
else:
    flag = 0
    A = 1
    A *= calc(0,a[0]-1)

    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            flag = 1
            break
        A *= calc(a[i]+1,a[i+1]-1)
        A %= mod

    A *= calc(a[M-1]+1,N)
    A %= mod

    if flag == 1:
        print(0)
    else:
        print(A)


### FIXED CODE ###


N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())
a.append(100000000)
flag = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break

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

for i in range(N-1):
    if i+1 == a[tmp]:
        dp[i+2] = dp[i]
    elif i == a[tmp]:
        dp[i+2] = dp[i+1]
        tmp += 1
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
bc = []
for _ in range(M):
  b, c = map(int, input().split())
  bc += [-c]*b

heapq.heapify(A)
heapq.heapify(bc)
while True:
  a = heapq.heappop(A)
  c = -1 * heapq.heappop(bc)
  if a < c:
    heapq.heappush(A, c)
  else:
    heapq.heappush(A, a)
    break
  if len(bc) == 0:
    break

print(sum(A))




### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x:x[1], reverse=True)
st = 0
flag = True
for i in range(m):
  b, c = bc[i]
  if flag and st < n:
    for i in range(st, min(b+st, n)):
      if a[i] < c:
        a[i] = c
      else:
        flag = False
        break
    st += b
  else:
    break

print(sum(a))
### BUGGY CODE ###


N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

max_SumA = (M*(M+1))//2
AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の数
noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:
        flag = 1
        for idx in range(M-a,-1,-1):
            if memo[idx] == 0:#仕事が請けられる
                ans += b
                memo[idx]=1
                flag = 0
                break
        if flag ==1:
            noMore = a
    
print(ans)
    


### FIXED CODE ###


N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の日
work = [float('inf')]*(10**5+1)

noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:
        flag = 1
        for idx in range(min(M-a,work[a]),-1,-1):
            if memo[idx] == 0:#仕事が請けられる
                ans += b
                memo[idx]=1
                flag = 0
                work[a] = idx
                break
        if flag ==1:
            noMore = a
    
print(ans)
### BUGGY CODE ###

A = 0
B = 1
C = 2

table = {"A": A, "B": B, "C": C}

s = [table[c] for c in input()]

i = 0
imax = len(s) - 2
count = 0
while i < imax:
	if s[i] == A and s[i + 1] == B and s[i + 2] == C:
		s[i] = B
		s[i + 1] = C
		s[i + 2] = A
		count += 1
		if i > 0:
			i -= 1
	else:
		i += 1

print(count)


### FIXED CODE ###

A = 0
B = 1
C = 2

table = {"A": A, "B": B, "C": C}

s = [table[c] for c in input()]
s.reverse()

total = 0
bc_count = 0
prev = None
for c in s:
	if c == A:
		if prev == C:
			bc_count = 0
		else:
			total += bc_count
	elif c == B:
		if prev == C:
			bc_count += 1
		else:
			bc_count = 0
	elif c == C:
		if prev == C:
			bc_count = 0
	prev = c

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

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    a, b = [int(_) for _ in input().split()]
    diff = b - a

    cur_tower = 1
    ts = []
    for add in range(2, 1000):
        next_tower = cur_tower + add
        ts.append((cur_tower, next_tower))

        cur_tower = next_tower

    for snow in range(1, 499951):
        if (a + snow, b + snow) in ts:
            print(snow)
            break

main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    a, b = [int(_) for _ in input().split()]
    diff = b - a

    tower = 0
    ts = []
    for add in range(1, 1000):
        tower += add
        ts.append(tower)

    print(ts[diff-2] - a)

main()
### BUGGY CODE ###

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

### FIXED CODE ###

k,s=input().split()
k=int(k)
s=int(s)
cnt=0
for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if z>=0 and z<=k:
      cnt+=1
print(cnt)