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

s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = (num + (10 ** i) * s_array[len_s - i - 1])
    mod_array[num%mod] += 1

ans = 0
for i in mod_array:
    ans += (i * (i - 1)) / 2

print(int(ans))

### FIXED CODE ###

s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = pow(10, i, mod) * s_array[len_s - i - 1] + num
    num %= mod
    mod_array[num] += 1

ans = 0
for i in mod_array:
    ans += (i * (i - 1)) / 2

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

n, m = map(int, input().split())
jobs = []

for i in range(n):
    a, b = map(int, input().split())
    jobs.append([a,b])

jobs_sorted = sorted(jobs, key=lambda x:(x[0],-x[1]))

days = [0 for i in range(m)]
for i in range(n):
    # print(jobs_sorted[i])
    if jobs_sorted[i][0] <= m:
        for j in range(m - jobs_sorted[i][0], -1, -1):
            if days[j] < jobs_sorted[i][1]:
                days.insert(j + 1, jobs_sorted[i][1])
                del days[0]
                break
    # print(days)

print(sum(days))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
jobs = dict()

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [-b]
    else:
        jobs[a].append(-b)
# print(jobs)
sum_money = 0
money_list = [0]
heapq.heapify(money_list)
for i in range(1, m+1):
    if i in jobs.keys():
        for money in jobs[i]:
            heapq.heappush(money_list, money)
    # print(money_list)
    max_money = -heapq.heappop(money_list)
    sum_money += max_money
    if max_money == 0:
        heapq.heappush(money_list, 0)
print(sum_money)
### BUGGY CODE ###

N,M = map(int,input().split())
L = [0]*M
R = [0]*M

for i in range(M):
    L[i],R[i] = map(int,input().split())
    

d={}

cnt = 0

for i in range(M):
    l = L[i]
    r=R[i]
    
    for j in range(l,r+1):
        
        if j in d:
            d[j] += 1
        else:
            d[j] = 1
            
        if d[j] >= M:
            cnt+=1
    
print(cnt)    

### FIXED CODE ###

N,M = map(int,input().split())
L = [0]*M
R = [0]*M

for i in range(M):
    L[i],R[i] = map(int,input().split())
    
L.sort()
R.sort()

l= L[len(L)-1]
r = R[0]

cnt =0 

for i in range(l,r+1):
    cnt+=1

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

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

ans = "Yes"

for i in range(1, N-1):

    if H[i] > H[i+1] and max(H[0: i]) - 1 > min(H[i: N]) and ans == "Yes":
        ans = "No"

print(ans)

### FIXED CODE ###

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

flag = True

for i in range(N-1, 0, -1):
    if H[i-1] - 1 == H[i]:
        H[i-1] -= 1
    elif H[i-1] - 1 > H[i]:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]

d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(1,k+1):
        if 0 <= bx+i < he and l[bx+i][by] != "@" and d[bx+i][by] > dis:
            d[bx+i][by] = dis+1
            q.append((dis+1,bx+i,by))
        else:
            break
    for i in range(1,k+1):
        if 0 <= bx-i < he and l[bx-i][by] != "@" and d[bx-i][by] > dis:
            d[bx-i][by] = dis+1
            q.append((dis+1,bx-i,by))
        else:
            break
    for i in range(1,k+1):
        if 0 <= by+i < w and l[bx][by+i] != "@" and d[bx][by+i] > dis:        
            d[bx][by+i] = dis+1
            q.append((dis+1,bx,by+i))
        else:
            break
    for i in range(1,k+1):
        if 0 <= by-i < w and l[bx][by-i] != "@" and d[bx][by-i] > dis:
            d[bx][by-i] = dis+1
            q.append((dis+1,bx,by-i))
        else:
            break

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(4):
        for j in range(1,k+1):
            nx = bx+dx[i]*j
            ny = by+dy[i]*j
            if 0 > nx or 0 > ny or nx >= he  or ny >= w:
                break
            if l[nx][ny] == "@":
                break
            if d[nx][ny] <= dis:
                break
            if d[nx][ny] > dis+1:
                d[nx][ny] = dis+1
                q.append((dis+1,nx,ny))

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])
### BUGGY CODE ###

def integerCards(n, m, alist, bclist):

    ans = 0
    bcintegrationlist = []

    for bc in bclist:
        bcintegrationlist += [bc[1]]*bc[0]

    alist += bcintegrationlist
    alist.sort(reverse=True)

    return sum(alist[:n])

def main():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print(integerCards(n, m, alist, bclist))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def integerCards(n, m, alist, bclist):

    count = 0
    alist.sort()
    bclist.sort(key=lambda x: x[1], reverse=True)

    for b, c in bclist:
        for _ in range(b):
            if alist[count] < c:
                alist[count] = c
                count += 1
            else:
                break
            if count == n:
                break
        if count == n:
            break

    return sum(alist)

def main():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print(integerCards(n, m, alist, bclist))

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

def ff(x,y,z):
    return(x**2+y**2+z**2+x*y+y*z+z*x)

n=int(input())
an = []
for i in range(1,50):
    for j in range(1,50):
        for k in range(1,50):
            wk=ff(i,j,k)
            if wk<=n:
                an.append(wk)
            else:
                break

for i in range(1,n+1):
    print(an.count(i))

### FIXED CODE ###

def ff(x,y,z):
    return(x**2+y**2+z**2+x*y+y*z+z*x)

n=int(input())
an=[0]*n
for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            wk=ff(i,j,k)
            if wk<=n:
                an[wk-1]+=1
for i in an:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S=sum(D2)
    D0=D2.count(0)
    R=(n-1)//k
    ANS=R*(k-D0) - S//m*R-(S%m*R+x%m)//m 

    x2=(x+S*R)%m
    rest=n-R*k-1
    S2=sum(D2[:rest])
    DR0=D2[:rest].count(0)
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

def sum_count(A):
    S=0
    C=0
    for a in A:
        if a==0:
            C+=1
        else:
            S+=a
    return S,C

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S,D0=sum_count(D2)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 
    x2=(x+S*R)%m
    rest=n-R*k-1
    S2,DR0=sum_count(D2[:rest])
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)
### BUGGY CODE ###

import math
def isPrime(n):
    if n == 2:
        return True
    if n%2 == 0:
        return False
    nMax = int(math.sqrt(n))+1
    for i in range(3, nMax+1):
        if n%i == 0: return False
    else: return True
         
while 1:
    try:
        n = input()
        c = 0
        for i in range(2,n+1):
            if isPrime(i) is True:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = []
y_list = []
for i in range(N):
    x, y = map(int, input().split())
    x_list.append([x, i])
    y_list.append([y, i])

x_list.sort()
y_list.sort()
adj = []
for i in range(N-1):
    adj.append([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
    adj.append([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

print(kruskal(adj, 2 * (N - 1)))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

N=int(input())
A=list(map(int,input().split()))
ans=A.pop(0)
for i in A: ans=ans*i
print(ans if ans<=10**18 else -1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=A.pop(-1)
if 0 in A:
    print(0)
else:
    for i in range(N-1):
        ans=ans*A[N-(i+2)]
        if ans > (10**18): break
        if ans == 0: break
    print(ans if ans<=10**18 else -1)
### BUGGY CODE ###

def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]

        mul *= 10
        dp = next_dp

    print(dp[5] % mod)
    
resolve()

### FIXED CODE ###

def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5])
    
resolve()
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
x=[]
for i in range(m):x.append(list(map(int,input().split()))[::-1])
x.sort(reverse=1)
s=0
for i,j in x:
  for k in range(j):
    if i<a[0]:s=1;break
    del a[0];a.append(i)
  if s==1:break
print(sum(a))

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a=deque(a)
x=[]
for i in range(m):x.append(list(map(int,input().split()))[::-1])
x.sort(reverse=1)
for i,j in x:
  for k in range(j):
    if i<=a[0]:print(sum(a));exit()
    a.popleft();a.append(i)
print(sum(a))
### BUGGY CODE ###

S = list(input())[::-1]
N = len(S)
M = [(int(S[i])*10**i)%2019 for i in range(N)]
SS = [M[0]]
for i in range(1,N):
    
    SS.append((SS[-1]+M[i])%2019)
count = [0]*2019
for i in range(N):
    count[SS[i]] += 1

ans = 0
for c in range(len(count)):
    if c==0:
        ans += (count[c] * (count[c] + 1)) // 2
    ans += (count[c] * (count[c] - 1)) // 2

print(ans)

### FIXED CODE ###

import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
sys.setrecursionlimit(500000)

S = list(input())[::-1]
N = len(S)
D = [1]
for i in range(N):
    D.append(D[-1]*10%2019)
M = [(int(S[i])*D[i])%2019 for i in range(N)]
SS = [M[0]]
for i in range(1,N):
    SS.append((SS[-1]+M[i])%2019)
count = [0]*2019
for i in range(N):
    count[SS[i]] += 1

ans = 0
for c in range(len(count)):
    if c==0:
        ans += count[c]
    ans += (count[c] * (count[c] - 1)) // 2

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

from queue import Queue
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())

    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put((h, w))
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append((h-1, w))
            if h != H-1:
                Next[h][w].append((h+1, w))
            if w != 0:
                Next[h][w].append((h, w-1))
            if w != W-1:
                Next[h][w].append((h, w+1))

    c = -1
    for _ in range(H+W+2):
        if l == 0:
            break
        nl = 0
        for _ in range(l):
            (h, w) = q.get()
            for nh, nw in Next[h][w]:
                if not checked[nh][nw]:
                    q.put((nh, nw))
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1
    print(c)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

[a,op,b]=[x for x in input().split()]
a=int(a)
b=int(b)
while True:
    if a==0 and b==0:
        break
    elif op=="+":
        print(a+b)
    elif op=="-":
        print(a-b)
    elif op=="*":
        print(a*b)
    else:
        print(a//b)

### FIXED CODE ###

while True:
    [a,b,c]=[x for x in input().split()]
    [a,c]=[int(a),int(c)]
    op=b
    if op=="?":
        break
    elif op=="+":
        print(a+c)
    elif op=="-":
        print(a-c)
    elif op=="*":
        print(a*c)
    else:
        print(a//c)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc089/tasks/abc089_c
import itertools
N = int(input())
S = [input() for _ in range(N)]
march = [0]*max(N,3)
ans = 0
for s in S:
    if s[0] == "M":
        march[0] +=1
    if s[0] == "A":
        march[1] +=1
    if s[0] == "R":
        march[2] +=1
    if s[0] == "C":
        march[3] +=1
    if s[0] == "H":
        march[4] +=1

for i,j,k in itertools.combinations(march,3):
    ans += i*j*k
print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc089/tasks/abc089_c
import itertools
N = int(input())
S = [input() for _ in range(N)]
M,A,R,C,H = 0,0,0,0,0
ans = 0
for s in S:
    if s[0] == "M":
        M +=1
    if s[0] == "A":
        A +=1
    if s[0] == "R":
        R +=1
    if s[0] == "C":
        C +=1
    if s[0] == "H":
        H +=1

for i,j,k in itertools.combinations([M,A,R,C,H],3):
    ans += i*j*k
print(ans)
### BUGGY CODE ###

def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    c = [[0 for j in range(len(Y))] for i in range(len(X))]
    maxl = 0
    
    for i in range(1,len(X)):
        for j in range(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(raw_input())
 
for i in range(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

### FIXED CODE ###

def lcs(X, Y):
    #X = " " + X
    #Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c2 = [0 for i in xrange(len(Y) + 1)]
    #maxl = 0
     
    for i in xrange(len(X)):
        c1 = c2 + []
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                c2[j + 1] = c1[j] + 1
            elif c2[j + 1] < c2[j]:
                c2[j + 1] = c2[j]
    return c2[-1]
n = int(raw_input())
  
for i in xrange(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)
### BUGGY CODE ###

import sys

def is_prime(x,y):
    while(y < x):
        if(x % y == 0):
            return 0
        y += 2
    return 1

a = ""
l = []
count = 0
for input in sys.stdin:
    a += input
l = sorted(set(a.split()))
for input in l:
    if(int(input) > 2 and int(input) % 2 != 0 and is_prime(int(input),3)):
        count += 1
    elif(int(input) == 2):
        count += 1
print count


### FIXED CODE ###

import sys

def is_prime(x):
    if(x <= 3 and x > 1):
        return True
    elif(x % 2 == 0 or x % 3 == 0 or x < 2):
        return False
    i = 5
    while(i * i <= x):
        if(x % i == 0 or x % (i + 2) == 0):
            return False
        i += 6
    return True

l = []
count = 0
for input in sys.stdin:
    l.append(int(input))
for data in range(1,len(l)):
    if(is_prime(l[data]) == True):
        count += 1
print count
### BUGGY CODE ###

import sys
sys.setrecursionlimit(220000)

n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

bit = [0 for _ in range(n)]

def dfs(k):
    for i in l[k]:
        if bit[i]==0:
            bit[i] = 1
            value[i] += value[k]
            dfs(i)
bit[0] = 1
dfs(0)
print(*value)


### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

bit = [0 for _ in range(n)]
"""
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)
"""
d = deque([0])
while d:
    a = d.popleft()
    bit[a] = 1
    for i in l[a]:
        if bit[i]==0:
            d.append(i)
            value[i] += value[a]
        

print(*value)
### BUGGY CODE ###

from collections import Counter
n,m = map(int,input().split())
a = list(map(int,input().split()))
for _ in range(m):
    b,c = map(int,input().split())
    a = a + [c]*b
a = Counter(a)
b = sorted(a.keys(),reverse = True)
x = 0
i = 0
s = 0
#print(b)
#print(a)
while x<n and i<len(b):
    if (x+a[b[i]]) > (n-1):
        temp = (n-x)
        x = x + temp
        s = s + b[i]*(temp)
        #print(temp,x,s)
        i+=1
    else:
        x = x + a[b[i]]
        s = s + b[i]*a[b[i]]
        #print(s,x)
        i+=1
print(s)

### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
i=0
j=0
#print(a,x)
s=0
p = 0
x1 = len(x)
while p<n:
    if (j == x1) or (a[i]>x[j][0]):
        s+=a[i]
        p+=1
        i+=1
    else:
        if (p + x[j][1]) > n:
            temp = n - p
            p+=temp
            s = s + x[j][0]*temp
        else:
            p = p + x[j][1]
            s = s + x[j][0]*x[j][1]
        #print(y)
        j+=1
print(s)