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

import bisect
n=int(raw_input())
a=map(int,raw_input().split())
b=sorted([(a[i],i+1) for i in range(n)])
s=[0,n+1]
ans=0
for c,j in b:
    k=bisect.bisect(s,j)
    ans+=c*(s[k]-j)*(j-s[k-1])
    bisect.insort(s,j)
print ans


### FIXED CODE ###

n=int(raw_input())
a=map(int,raw_input().split())
def f():
    s=[(0,-1)]
    x=[0]*(n+1)
    for i,j in enumerate(a):
        while s[-1][0]>j:s.pop()
        x[j]=i-s[-1][1]
        s.append((j,i))
    return x
l=f()
a.reverse()
r=f()
print sum([i*l[i]*r[i] for i in a])
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_cumsum, B_cumsum = [0], [0]

for i in range(n):
    A_cumsum.append(A_cumsum[i] + A[i])
    
for j in range(m):
    B_cumsum.append(B_cumsum[j] + B[j])
    
ans = 0

for i, a in enumerate(A_cumsum):
    if a > k:
        break
    
    for j, b in enumerate(B_cumsum):
        if (a + b) > k:
            break
        elif (i + j) < ans:
            pass
        else:
            ans = (i + j)

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_cumsum, B_cumsum = [0], [0]

for i in range(n):
    A_cumsum.append(A_cumsum[i] + A[i])
    
for j in range(m):
    B_cumsum.append(B_cumsum[j] + B[j])
    
ans, j = 0, m

for i in range(n + 1): # 0を最初に代入した分
    if A_cumsum[i] > k:
        break
    while A_cumsum[i] + B_cumsum[j] > k:
        j -= 1
    ans = max(ans, i + j)

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

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
P = np.zeros((N), dtype='i')

INF = 10**18

ans = 0
for i in range(N):
    v = A[i]
    A[i] = INF
    P[i:] = np.arange(0, N - i)
    P[:i] = np.arange(1, i + 1)[::-1]
    # print('P', P)
    ans += np.count_nonzero(A + v == P)
    # if i >= 3:
    #     break
print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

L = defaultdict(int)
R = defaultdict(int)
for i, x in enumerate(A, 1):
    l = i + x
    r = i - x
    L[l] += 1
    R[r] += 1
# print('L', L)
# print('R', R)
ans = 0
for key, l_value in L.items():
    r_value = R[key]
    ans += l_value * r_value
print(ans)
# memo = defaultdict(int)
# answer = 0
# for i, x in enumerate(A, 1):
#     answer += memo[i - x]
#     memo[x + i] += 1

# print('memo', memo)
# print(answer)
### BUGGY CODE ###

A,B,K = map(int,input().split(" "))
list = []
for i in range(B-A+1):
    list.append(i+A)
#print(list)

if K*2 >= len(list):
    for i in range(len(list)):
        print(list[i])
else:
    for i in range(K):
        print(list[i])
    for i in range(K):
        print(list[i+len(list)-1-K+1])

### FIXED CODE ###

A,B,K = map(int,input().split(" "))
list = []

if B - A + 1 <= K * 2:
    for i in range(A,B+1):
        print(i)
else:
    count = 0
    for i in range(A,B+1):
        count += 1
        print(i)
        if count >= K:
            break
    count = 0
    for i in range(B-K+1,B+1):
        print(i)
### BUGGY CODE ###

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

def main():
    N=int(input())  #数値入力 「N」だけの入力のとき
    H=tuple(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
    ans = 0
    a = 0
    for i in range(N):
        a = 0
        if ans > N-i-1:
            break
        else:
            for j in range(N-i):
                if i+j == N-1:
                    if a > ans:
                        ans = a
                    break
                elif H[i+j] >= H[i+j+1]:
                    a += 1
                else:
                    if a > ans:
                        ans = a
                    break
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
ans = 0
cnt = 0
for ind,i in enumerate(H[:-1]):
    if(i>=H[ind+1]):
        cnt += 1
    else:
        cnt = 0
    ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    X = input()

    for i in range(N):
        count = 0
        if X[i] == "1":
            nX = int(X, 2) - 2 ** (N-1-i)
        if X[i] == "0":
            nX = int(X, 2) + 2 ** (N-1-i) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else: 
                if i != N-1:
                    if X[-1] == "0":
                        print(1)
                    else:
                        print(2)
                else:
                    print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
R = [0 for i in range(N)]

for i in range(min(A[-1], A[0]) + 1):
	R[0] = i
	fin = 1
	for j in range(1, N):
		R[j] = A[j - 1] - R[j - 1]
		# print(j, R[j])
		if R[j] < 0:
			fin = 0
			break
	# print(R)
	if fin == 1 and R[0] == A[-1] - R[-1]:
		for r in R:
			print(r * 2, end=" ")
		break

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = []
total = 0

for i in range(1, N, 2):
    total += A[i]
    
X.append(sum(A) - 2 * total)

for i in range(N - 1):
    X.append(int(2 * (A[i] - X[i] / 2)))
    
for i in range(len(X)):
    print(X[i], end = " ")
### BUGGY CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
bit = 0b0

ans = 0
for i in range(2**n):
    bag = []
    cost = []
    for j in range(n):
        if(((bit >> j) & 1) == 1):
            bag.append(v[j])
            cost.append(c[j])
        else:
            bag.append(0)
            cost.append(0)
    p = sum(bag) - sum(cost)
    if(p > ans):
        ans = p
    bit += 1
print(ans)

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
bag = 0
for i in range(n):
    if(c[i] <= v[i]):
        bag += v[i] - c[i]
print(bag)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
N, M = map(int, input().split())
graph = [[] * N for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    graph[L].append((R, D))
    graph[R].append((L, -D))


def dfs(node, dist):
    global visited
    global dists
    dists[node] = dist
    for next, d in graph[node]:
        if next in visited:
            if d + dist != dists[next]:
                print('No')
                sys.exit()
        else:
            visited.add(next)
            dfs(next, dist + d)


visited = set()
dists = [0] * N
for i in range(N):
    if i in visited:
        continue
    visited.add(i)
    dfs(i, 0)

print('Yes')


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
N, M = map(int, input().split())
graph = [[] * N for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    graph[L].append((R, D))
    graph[R].append((L, -D))


def dfs(node, dist):
    global visited
    global dists
    dists[node] = dist
    for next, d in graph[node]:
        if next in visited:
            if d + dist != dists[next]:
                print('No')
                sys.exit()
        else:
            visited.add(next)
            dfs(next, dist + d)


visited = set()
dists = [0] * N
for i in range(N):
    if i in visited:
        continue
    visited.add(i)
    dfs(i, 0)

print('Yes')
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

D = I()
c = [0] + LI()
s = [0] + [[0] + LI() for _ in range(D)]

last = [[0]*27 for _ in range(D+1)]
t = [0]

for i in range(1,D+1):
    r = 0
    manzoku = 0
    for j in range(1,27):
        m = s[i][j]
        for k in range(1,27):
            if k != j:
                m -= c[k]*(i-last[i-1][k])
            else:
                continue
        if j == 1:
            r = 1
            manzoku = m
        else:
            if manzoku < m:
                manzoku = m
                r = j
    t.append(r)
    for j in range(1,27):
        if j == r:
            last[i][j] = i
        else:
            last[i][j] = last[i-1][j]

M = D*26
dq = []
for i in range(1,D+1):
    for j in range(1,27):
        dq.append([i,j])

from copy import deepcopy

for i in range(M):
    d,q = dq[i]
    t0 = t[d]
    last2 = deepcopy(last)
    manzoku = s[d][q] - s[d][t0]
    for j in range(d,D+1):
        if j == d:
            last2[d][t0] = last2[d-1][t0]
            manzoku -= c[t0] * (d - last2[d][t0])
            last2[d][q] = d
            manzoku += c[q] * (d - last2[d-1][q])
        else:
            if last2[j][t0] == d:
                last2[j][t0] = last2[d-1][t0]
                manzoku -= c[t0] * (d - last2[d][t0])
            if last2[j][q] == last2[d-1][q]:
                last2[j][q] = d
                manzoku += c[q] * (d - last2[d-1][q])
    if manzoku > 0:
        t[d] = q
        last = last2

del t[0]

print(*t,sep='\n')

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

D = I()
c = [0] + LI()
s = [0] + [[0] + LI() for i in range(D)]

last = [0]*27

for i in range(1,D+1):
    r = 0
    manzokudo = 0
    for j in range(1,27):
        m = s[i][j]
        for k in range(1,27):
            if k != j:
                m -= c[k]*(i-last[k])
            else:
                continue
        if j == 1:
            r = 1
            manzokudo = m
        else:
            if manzokudo < m:
                manzokudo = m
                r = j
    print(r)
    last[r] = i
### BUGGY CODE ###

while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	ref = []
	for i in a:
		ref += [i+j for j in ref]
		ref.append(i)
	print min(abs(sum(a)-2*i) for i in ref)

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
            ans[r] %= mod
print(*ans)


### FIXED CODE ###

P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
            ans[r] %= mod
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from heapq import heappop, heappush

N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)
### BUGGY CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())
N = len(X)
st.append(X[0])
X.pop(0)
#for i in range(len(X)-2):
for i in range(N-1):
    st.append(X[0])
    X.pop(0)
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)


### FIXED CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())
N = len(X)
X.reverse()
st.append(X[-1])
X.pop()
#for i in range(len(X)-2):
for i in range(N-1):
    st.append(X[-1])
    X.pop()
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)
### BUGGY CODE ###

n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    for j in range(m):
        if (j + 1) % i == 0:
            x[j] += 1

for i in ints:
    if x[i-1] == 1:
        cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    if x[i-1] >= 2:
        continue
    for j in range(m // i):

        x[i * (j + 1) - 1] += 1

for i in ints:
    if x[i - 1] == 1:
        cnt += 1

print(cnt)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

dp = dict()


def f(t):
    x, y, z = t
    return A[x] + B[y] + C[z]


def main():
    done = []

    for k in range(K):
        if done == []:
            t = (0, 0, 0)
            done.append(t)
            print (f(t))
            continue

        temp = 0
        for d in done:
            x, y, z = d
            KOUHO = [(x, y, z+1), (x, y+1, z), (x+1, y, z)]
            for kouho in KOUHO:
                if kouho[0] == X:
                    continue
                if kouho[1] == Y:
                    continue
                if kouho[2] == Z:
                    continue
                if kouho in done:
                    continue
                if f(kouho) > temp:
                    toadd = kouho
                    temp = f(kouho)

        done.append(toadd)
        print(temp)


if __name__ == '__main__':
    main()


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

kouho = set()
done = set()


def f(t):
    x, y, z = t
    if x >= X or y >= Y or z >= Z:
        return 0
    return A[x] + B[y] + C[z]


def main():
    start = (f((0, 0, 0)), (0, 0, 0))
    kouho.add(start)
    done.add(start)

    for k in range(K):
        d = max(kouho)
        kouho.remove(d)

        x, y, z = d[1]
        toadd = [(x, y, z+1), (x, y+1, z), (x+1, y, z)]
        for ta in toadd:
            t = (f(ta), ta)
            if t in done:
                continue
            kouho.add(t)
            done.add(t)

        print(d[0])


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

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

### FIXED CODE ###

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

K = int(input())

if K % 2 == 0:
    print(-1)
    exit()

amari = 0

for i in range(1, 10**7):
    amari *= 10
    amari += 7
    amari %= K
    if amari == 0:
        print(i)
        exit()

print(-1)

### FIXED CODE ###

K = int(input())

if K % 2 == 0:
    print(-1)
    exit()

amari = 0

for i in range(1, 10**7):
    amari *= 10
    amari += 7
    amari %= K
    if amari == 0:
        print(i)
        exit()

print(-1)
### BUGGY CODE ###

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

ans = sum(H)

for n in range(1,min(N+1,K+1)):
    ans -= sorted(H)[-n]

print(ans)


### FIXED CODE ###

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

cnt = 0
H.sort(reverse=True)

if K >= N:
    print(0)
else:
    print(sum(H[K:]))
### BUGGY CODE ###

from itertools import permutations, combinations
n = int(input())
s = []
for _ in range(n):
  s.append(input())
 
ilist = []
for a in range(len(s)):
  ilist.append(list(s[a]))
 
for ss in range(len(ilist)):
  ilist[ss].sort()
 
li = list(combinations(ilist, 2))
ans = 0
 
for b in range(len(li)):
  if(li[b][0] == li[b][1]):
    ans += 1
print(ans)

### FIXED CODE ###

from collections import *
 
n = int(input())
dic = defaultdict(int)
for i in range(n):
  dic["".join(sorted(input()))] += 1
 
ans = 0
for k,v in dic.items(): 
  ans += int(v*(v-1)/2)
  #ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

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

ret = 0
i = 2
while A >= i and B >= i :
    flg = False
    while A % i == 0 and B % i == 0 :
        A //= i
        B //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

### FIXED CODE ###

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)
### BUGGY CODE ###

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

### FIXED CODE ###

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

import heapq

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

for _ in range(m):
    b, c = map(int, input().split())
    l.append((b, c))

for b, c in l:
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

for _ in range(m):
    b, c = map(int, input().split())
    l.append((b, c))

l = sorted(l, key=lambda x: x[1], reverse=True)

for b, c in l:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

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

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
target = [list(map(int, input().split())) for i in range(M)]
#target = sorted(target, key = lambda x:x[1], reverse=True)
#print(target)

'''
4 4
1 3
2 2
1 1
2 4


'''

tmp = []

for t in target:
    for i in range(t[0]):
        tmp.append(t[1])
tmp.sort(reverse=True)
A.extend(tmp)
A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
target = [list(map(int, input().split())) for i in range(M)]
target = sorted(target, key = lambda x:x[1], reverse=True)
# print(target)

'''
4 4
1 3
2 2
1 1
2 4


'''


for t in target:
    A.extend([t[1]] * t[0])
    if len(A) > N * 2:
        break
A.sort(reverse=True)

print(sum(A[:N]))