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

N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
ans = sum(sum(A[i]) for i in range(N))//2

for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            if A[i][j] > A[i][k]+A[j][k]:
                print(-1)
                exit()
            elif i != k and j != k and A[i][j] == A[i][k]+A[j][k]:
                ans -= A[i][j]


print(ans)


### FIXED CODE ###

N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
roads = [[True]*N for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k]+A[j][k]:
                print(-1)
                exit()
            if i == j:
                roads[i][j] = False
            if i != k and j != k and A[i][j] == A[i][k]+A[j][k]:
                roads[i][j] = False


ans = 0
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] is True:
            ans += A[i][j]
print(ans)
### BUGGY CODE ###

K = int(input())

que = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(K):
    que.pop(0)
    temp = que[0]
    if i == K:
        break
    mod = temp % 10
    if mod == 0:
        que += [temp*10+(mod), temp*10+(mod)+1]
    elif temp % 10 == 9:
        que += [temp*10+(mod)-1, temp*10+(mod)]
    else:
        que += [temp*10+(mod)-1, temp*10+(mod), temp*10+(mod)+1]

print(que[0])


### FIXED CODE ###

K = int(input())

que = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(K):
    temp = que[i]
    if i == K-1:
        print(que[i])
        break
    mod = temp % 10
    if mod == 0:
        que += [temp*10+(mod), temp*10+(mod)+1]
    elif temp % 10 == 9:
        que += [temp*10+(mod)-1, temp*10+(mod)]
    else:
        que += [temp*10+(mod)-1, temp*10+(mod), temp*10+(mod)+1]
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    N = int(input())
    A = [None for _ in range(N)]
    INF = 10**12
    for i in range(N):
        A[i] = list(map(int, input().split()))

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
            if flag:
                adj[i][j] = A[i][j]
    ans = 0
    for i in range(N):
        ans += sum(adj[i])
    print(ans//2)
    # print(adj)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = [None for _ in range(N)]
    INF = 10**12
    for i in range(N):
        A[i] = list(map(int, input().split()))

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
            if flag:
                adj[i][j] = A[i][j]
    ans = 0
    for i in range(N):
        ans += sum(adj[i])
    print(ans//2)

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

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    elif A[i] > B[i]: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    if sum(S_ba) <= now: break
    now += S_ab[i]
    ans += 1

print(ans)


### FIXED CODE ###

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    elif A[i] > B[i]: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
rem = sum(S_ba)
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1

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

N = int(input())

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


min = float('INF')

for i in range(N-1):
    sunek = A[0:i+1]
    araig = A[i+1:N]
    min_temp = (abs(sum(sunek)-sum(araig)))

    if min_temp < min:
        min = min_temp

print(min)

### FIXED CODE ###

import sys

N= int(input())

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


S = [0]*(len(A)+1)

for i in range(1, len(S), 1):

    S[i] = S[i-1] + A[i-1]

x = 0
y = 0
min = float('inf')

for i in range(1, N, 1):
    x = S[i]
    y = S[len(S)-1] - S[i]

    if min > abs(x-y):
        min = abs(x-y)
print(min)
### BUGGY CODE ###

S = input()

# do shakutori


Q = [0]
for i in range(len(S)-1, -1, -1):
    Q.append(int(S[i:]) % 2019)
# print(Q)

import collections
dct = dict(collections.Counter(Q))
# print(dct)
ans = 0
for val in dct.values():
    ans += val * (val - 1) // 2
print(ans)



### FIXED CODE ###

S = input()

# do shakutori
#以下が an mod p を求めるソースコードです.
def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

Q = [0]
for i in range(len(S)-1, -1, -1):
    pow = len(S) - i - 1
    Q.append((Q[-1] + power_func(10, pow, 2019) * int(S[i])) % 2019)
# print(Q)

import collections
dct = dict(collections.Counter(Q))
# print(dct)
ans = 0
for val in dct.values():
    ans += val * (val - 1) // 2
print(ans)
### BUGGY CODE ###

import math
N= int(input())
a=0
b=0
for i in range(1,N+1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            b=math.gcd(i,j)
            a+=math.gcd(b,k)
print(a)

### FIXED CODE ###

import math
N= int(input())
a=0
b=0
for i in range(1,N+1):
    for j in range(1, N + 1):
        b = math.gcd(i, j)
        for k in range(1, N + 1):
            a+=math.gcd(b,k)
print(a)
### BUGGY CODE ###

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

### FIXED CODE ###

import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))
### BUGGY CODE ###


def main(n,a):
    s=a[0]+a[1]
    z=0
    for ai in a[2:]:
        z^=ai
    # i+j=s,i<=a[0],i^j=z となるi,jを探す
    # i+j=i^j+2*(i & j)
    # s = z + 2*(i & j)
    # i & j = (s-z)/2 = d
    # z = 2*(i & j) - s = i ^ j
    # d = (s-z) / 2
    # z = x^y , x&y=0
    # d^x,d^yは条件を満たす。d^x+d^y=d^x^d^y + 2*((d^x)&(d^y))= z + 2*d = s
    # (d^x)^(d^y)=x^y=z
    # (d^x)&(d^y)=d (z & d = 0 のときのみ)
    if s-z<0 or (s-z)%2==1:return -1
    d=(s-z)//2
    if d&z!=0:return -1
    part=[]
    i=0
    while z//pow(2,i):
        if (z//pow(2,i))%2==1:part.append(pow(2,i))
        i+=1
    ans=float('inf')
    k=len(part)
    for i in range(2**k):
        x=0
        y=0
        for j in range(k):
            if (i>>j)&1:
                x+=part[j]
            else:
                y+=part[j]
        u=d^x
        v=d^y
        if u+v==s and u<=a[0] and u!=0:
            ans=min(ans,a[0]-u)
    return ans if ans!=float('inf') else -1





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

### FIXED CODE ###

def main(n,a):
    s=a[0]+a[1]
    z=0
    for ai in a[2:]:
        z^=ai
    # i+j=s,i<=a[0],i^j=z となるi,jを探す
    # i+j=i^j+2*(i & j)
    # s = z + 2*(i & j)
    # i & j = (s-z)/2 = d
    # z = 2*(i & j) - s = i ^ j
    # d = (s-z) / 2
    # z = x^y , x&y=0
    # d^x,d^yは条件を満たす。d^x+d^y=d^x^d^y + 2*((d^x)&(d^y))= z + 2*d = s
    # (d^x)^(d^y)=x^y=z
    # (d^x)&(d^y)=d (z & d = 0 のときのみ)
    if s-z<0 or (s-z)%2==1:return -1
    d=(s-z)//2
    if d&z!=0:return -1
    if not d<=a[0]:return -1
    part=[]
    i=0
    while z//pow(2,i):
        if (z//pow(2,i))%2==1:part.append(pow(2,i))
        i+=1
    ans=float('inf')
    k=len(part)
    x=0
    while part:
        tmp=part.pop()
        if d^(x+tmp)<=a[0]:
            x+=tmp
    return a[0]-(d^x) if d^x else -1


n=int(input())
a=list(map(int,input().split()))
print(main(n,a))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
M = 1
for i in L:
  M *= i
if M > 1000000000000000000:
  print(-1)
else:
  print(M)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
M = 1
for i in L:
  M *= i
  if M > 10**18:
    M = -1
    break
print(M)
### BUGGY CODE ###

import sys
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
Ls = []
Rs = []
ps = []
qs = []
counter = M

d = []
for i in range(N):
    d.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
#    print(line.strip().split(' '))
#    L, R == line.strip().split(' ')
    if not flag:
        for i in range(L):
            for j in range(N - R + 1):
                d[i][R + j - 1] += 1
        Ls.append(L)
        Rs.append(R)
        counter -= 1
        if counter == 0:
            flag = True
    else:
        print(d[L-1][R-1])

### FIXED CODE ###

import sys
from itertools import accumulate
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
counter = M

d = []
d2 = []
for i in range(N):
    d.append([0] * N)
for i in range(N):
    d2.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        d[L-1][R-1] += 1
#        for i in range(L):
#            for j in range(N - R + 1):
#                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
#            print(d)
            for i in range(N):
                d[i] = d[i][::-1]
#            print(d)
            for i in range(N):
                if i == 0:
                    d[N-1] = list(accumulate(d[N-1][::-1]))[::-1]
                else:
                    for j in range(N):
                        if j == 0:
                            temp = d[N-1-i][N-1-j]
                        else:
                            temp += d[N-1-i][N-1-j]
                        d[N-1-i][N-1-j] = d[N-i][N-1-j] + temp
#            print(d)
#            for x in d:
#                print(x)
            flag = True
    else:
        print(d[L-1][N-R])
### BUGGY CODE ###

# 解説AC
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]

ans = float("inf")

# A[i]: 最小値X
for i in range(N):
    # 最大値Yの候補
    can = []

    # A[left:right]: A[i]以上の連続部分列
    left = 0
    while left < N:
        right = left
        while right < N and A[i] <= A[right]:
            right += 1

        # 連続部分列長
        L = right - left

        tmp = sorted([A[j] for j in range(left, right)])
        can += tmp[:max(0, L - K + 1)]

        left = right + 1
    
    # Q番目に小さいものがYの最小値
    can.sort()
    if len(can) >= Q:
        ans = min(ans, can[Q - 1] - A[i])

print(ans)

### FIXED CODE ###

# 解説AC
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]

def main():
    ans = float("inf")

    # A[i]: 最小値X
    for i in range(N):
        # 最大値Yの候補
        can = []

        # A[left:right]: A[i]以上の連続部分列
        left = 0
        while left < N:
            right = left
            while right < N and A[i] <= A[right]:
                right += 1

            # 連続部分列長
            L = right - left

            tmp = sorted([A[j] for j in range(left, right)])
            can += tmp[:max(0, L - K + 1)]

            left = right + 1
        
        # Q番目に小さいものがYの最小値
        can.sort()
        if len(can) >= Q:
            ans = min(ans, can[Q - 1] - A[i])

    print(ans)

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

from collections import deque
N,M=map(int,input().split())
edge=[[] for i in range(N)]
visited=[-1 for i in range(N)]
dist=[1000000000 for i in range(N)]
last=[-1 for i in range(N)]
i=0
dist[0]=0
for i in range(M):
    A,B=map(int,input().split())
    edge[A-1].append(B-1)
    edge[B-1].append(A-1)
Q=deque()
Q.append(0)
while Q:
    i=Q.popleft()
    for j in edge[i]:
        if dist[j]>dist[i]+1:
            dist[j]=dist[i]+1
            last[j]=i+1
        if visited[j]==-1 and (j not in Q):
            Q.append(j)
    visited[i]=1
print("Yes")
for i in range(1,N):
  print(last[i])

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
edge=[[] for i in range(N)]
visited=[-1 for i in range(N)]
dist=[1000000000 for i in range(N)]
last=[-1 for i in range(N)]
i=0
dist[0]=0
for i in range(M):
    A,B=map(int,input().split())
    edge[A-1].append(B-1)
    edge[B-1].append(A-1)
Q=deque()
Q.append(0)
while Q:
    i=Q.popleft()
    if visited[i]==-1:
        for j in edge[i]:
            if dist[j]>dist[i]+1:
                dist[j]=dist[i]+1
                last[j]=i+1
            if visited[j]==-1:
                Q.append(j)
    visited[i]=1
print("Yes")
for i in range(1,N):
	print(last[i])
### BUGGY CODE ###

n = int(input())
ans=n
for i in range(n+1):
  cnt=0
  t=i
  while t>0:
    cnt+=t%6
    t//=6
  s=n-i
  while s>0:
    cnt+=s%9
    s//9
  min(ans,cnt)
print(ans)

### FIXED CODE ###

n = int(input())
ans=n
for i in range(n+1):
  cnt=0
  t=i
  while t>0:
    cnt+=t%6
    t//=6
  s=n-i
  while s>0:
    cnt+=s%9
    s//=9
  ans = min(ans,cnt)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(d) for d in input().split()]

MOD = int(1e9+7)

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        t = ((A[i] * A[j]) % MOD + ans)% MOD
        ans = t

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(d) for d in input().split()]

MOD = int(1e9+7)

A_cum = [0]
for i in range(N):
    A_cum.append((A_cum[-1] + A[i]) % MOD)

ans = 0
for i in range(N-1):
    t = (A[i] * (A_cum[-1] - A_cum[i+1]) % MOD ) % MOD
    ans = (t + ans)% MOD

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


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

hanten=0
for i in range(n):
    Q = input()
    if int(Q[0])==1:
        hanten+=1 
    elif int(Q[0])==2 :
        if hanten%2 == int(Q[2])-1 :
            s= Q[4]+s
        else:
            s= s+Q[4]

if hanten%2 :
    s = s[::-1]
print(s)        





### FIXED CODE ###


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

hanten=0
s1=""
s2=""
for i in range(n):
    Q = input()
    if int(Q[0])==1:
        hanten+=1 
    elif int(Q[0])==2 :
        if hanten%2 == int(Q[2])-1 :
            s1= s1+Q[4]
        else:
            s2= s2+Q[4]

s1 = s1[::-1]
s = s1+s+s2

if hanten%2 :
    s = s[::-1]
print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from bisect import bisect_right

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        idxs[a] = i
    lowers = [0, N + 1]
    ans = 0
    for a, i in enumerate(idxs[1:], 1):
        j = bisect_right(lowers, i)
        l, r = lowers[j - 1], lowers[j]
        lowers = lowers[:j] + [i] + lowers[j:]
        ans += (i - l) * (r - i) * a

    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())
### BUGGY CODE ###

import itertools

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

ans = 0

MOD = 10**9 + 7

for v in itertools.combinations(a, k):
    ans += (max(v) - min(v))%MOD

print(ans%MOD)


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

ans = 0


a.sort()

for j in range(n):
    i = j +1
    if j <= n-k:
        minX = a[i-1]
        ans -= a[i-1]*cmb(n-i,k-1,mod)%mod
    if k -1 <= i:
        maxX = a[i-1]
        ans += a[i-1]*cmb(i-1,k-1,mod)%mod

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

N = int(input())
X = int(input(), 2)

def solve(X, cnt):
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    return solve(X, cnt+1)

for i in range(N):
    print(solve(X ^ 1 << (N - i - 1), 0))

### FIXED CODE ###

N = int(input())
X = list(input())
one = X.count('1')
L1 = [1]
L2 = [1]

for _ in range(N-1):
    if one - 1 == 0:
        L1.append(0)
    else:
        L1.append((L1[-1] * 2) % (one - 1))
    L2.append((L2[-1] * 2) % (one + 1))

x1 = 0
x2 = 0
power1 = 1
power2 = 1

for i in range(N):
    if X[N-i-1] == '1':
        if one - 1 != 0:
            x1 += power1
        x2 += power2
    power1 *= 2
    power2 *= 2
    if one - 1 != 0:
        power1 %= one - 1
    power2 %= one + 1

def solve(X, cnt):
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    return solve(X, cnt+1)

for i in range(N):
    if X[i] == '0':
        tmp = (x2 + L2[N-i-1]) % (one + 1)
        ans = solve(tmp, 0) + 1
    else:
        if one - 1 == 0:
            ans = 0
        else:
            tmp = (x1 - L1[N-i-1]) % (one - 1)
            ans = solve(tmp, 0) + 1
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=1
if 0 in a:
  print(0)
  exit(0)
for i in range(n):
    count=count*a[i]
if count>10**18:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
  exit()
for num in lis:
  ans *= num
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

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

out = 0

for i in set(a):
    cnt = 0
    for j in a:
        if j == i or j-1 == i or j+1 == i:
            cnt += 1
    out = max(out, cnt)

print(out)


### FIXED CODE ###

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

def func(a):
  count = [0] * (max(a)+1)

  for i in a:
      count[i] += 1

  max_n = 0
  for j in range(1, len(count)-1):
      max_n = max(max_n, count[j] + count[j-1] + count[j+1])
  max_n = max(max_n, count[-1] + count[-2])

  return max_n

print(n if len(set(a)) == 1 else func(a))
### BUGGY CODE ###

n,x = map(int,input().split())
a = list(map(int,input().split()))
a.append(x)
a.sort()
d = [1000000000]
e = []
flg = False
for i in range(len(a)-1):
  t = a[1+i] - a[i]
  e.append(t)
  if(t < d[0]):
    d.insert(0,t)
  if(t == 1):
    flg = True
    break
if(flg):
  print(1)
else:
  k = d[0]
  j = 2
  while True:
    s = int(k/j)
    if(k % j == 0):
      d.append(s)
    if(s < 1):
      break
    j += 1

  d.sort()
  l = len(d)
  ans = 1
  for i in range(l):
    u = list(map(lambda x: x% d[l - 1 - i],e))
    if(u.count(0) == n):
      ans = d[l-1-i]
      break
  print(ans)

### FIXED CODE ###

n,x = map(int,input().split())
a = list(map(int,input().split()))
a.append(x)
a.sort()
d = [1000000000]
e = []
flg = False
for i in range(len(a)-1):
  t = a[1+i] - a[i]
  e.append(t)
  if(t < d[0]):
    d.insert(0,t)
  if(t == 1):
    flg = True
    break
if(flg):
  print(1)
else:
  d.sort()
  l = len(d)
  ans = 1
  for i in range(l):
    u = list(map(lambda x: x% d[l - 1 - i],e))
    if(u.count(0) == n):
      ans = d[l-1-i]
      break
  if(ans == 1):
    k = d[0]
    f = []
    j = 2
    while True:
      s = int(k/j)
      if(k % j == 0):
        f.insert(0,s)
      if(s < 1):
        break
      j += 1
    q = len(f)
    for i in range(q):
      u = list(map(lambda x: x% f[q - 1 - i],e))
      if(u.count(0) == n):
        ans = f[q-1-i]
        break

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

def BC2D(s):
    n=len(s)
    index=[]
    for i in range(n-1):
        if s[i:i+2]=='BC':
            index.append(i)
    new_s=''
    for i in range(n):
        if i in index:
            new_s+='D'
        elif i-1 in index:
            new_s+=''
        else:
            new_s+=s[i]
    return new_s

def partition(s):
    s='B'+s+'C'
    group=[]
    n=len(s)
    left=0
    right=0
    for i in range(n-1):
        block=s[i:i+2]
        if block[0] in ['B','C'] and block[1] in ['A','D']:
            left=i
        if block[0] in ['A','D'] and block[1] in ['B','C']:
            right=i
            group.append(s[left:right+1])
    return group

def turningNo(s):
    totalCount=0
    count=0
    n=len(s)
    s=s[::-1]
    for i in range(n):
        if s[i]=='A':
            totalCount+=count
        if s[i]=='D':
            count+=1
    return totalCount

s=input()
s=BC2D(s)
G=partition(s)
answer=0
for element in G:
    answer+=turningNo(element)
print(answer)

### FIXED CODE ###

s=input()
s=s.replace("BC","D")
totalCount=0
count=0
for char in s:
    if char=="A":
        count+=1
    elif char=="D":
        totalCount+=count
    else:
        count=0
print(totalCount)
### BUGGY CODE ###

N = int(input())
MM = input().split()
total = 1
for i in MM:
  total = total*int(i)
if total > 10**18:
  print(-1)
else:
  print(total)

### FIXED CODE ###

N = int(input())
MM = input().split()
total = 1
for i in MM:
  total = total*int(i)

  if total > 10**18:
    break
for i in MM:
  if int(i) == 0:
    total = 0
if total > 10**18:
  print(-1)
else:
  print(total)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
operation = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
  a = [operation[i][1] if num == operation[i][0] else num for num in a]
  print(sum(a))

### FIXED CODE ###

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

from  collections import Counter

dict_a = Counter(a)
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s -= b*dict_a[b]
  s += c*dict_a[b]
  dict_a[c] += dict_a[b]
  dict_a[b] = 0
  print(s)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for i in range(0,M):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)

A.sort()

for i in range(0,M):
    for j in range(0,B[i]):
        if C[i] > A[0]:
            A[0] = C[i]
            A.sort()
        else:
            break

result = 0
for num in A:
    result += num
print(result)


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
cards = []
for i in range(0,N):
    cards.append((A[i],1))

for i in range(0,M):
    b,c = map(int,input().split())
    cards.append((c,b))

cards.sort()
cards.reverse()

result = 0
total = N
for num, cnt in cards:
    total -= cnt
    result += num*cnt
    if total < 0:
        result += num * total
        break
print(result)