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

S=input()
T=input()
lenS=len(S)

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)


### FIXED CODE ###

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

S=input()
T=input()
lenS=len(S)

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
A = []
B = []
for i in range(n):
    x, y = map(int, input().split())
    A.append(x)
    B.append(y)

ans = 0
while m > 0:
    idx = A.index(min(A))
    p = A.pop(idx)
    a = B.pop(idx)
    if a >= m:
        ans += p * m
        m -= a
    else:
        ans += p * a
        m -= a
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
A = []
B = []
for i in range(n):
    x, y = map(int, input().split())
    A.append(x)
    B.append(y)

ans = 0
for price, amount in sorted(zip(A, B)):
    ans += price * min(m, amount)
    m -= amount
    if m <= 0:
        break
print(ans)
### BUGGY CODE ###

from copy import deepcopy
import queue

def shortestpath(y0, x0, maze, h, w):
    step_cnt = [[-1] * w for _ in range(h)]
    q = queue.Queue()
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    dy = [-1, 0, 1, 0]
    dx = [0, -1, 0, 1]
    while not q.empty():
        y, x = q.get()
        maze[y][x] = '#'
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w and maze[y_next][x_next] == '.':
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]
 
h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
max_steps = -1

for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] == '#':
            continue
        copymaze = deepcopy(maze)
        max_steps = max(max_steps, shortestpath(y0, x0, copymaze, h, w))

print(max_steps)

### FIXED CODE ###

import queue

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = queue.Queue()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)
### BUGGY CODE ###

from queue import Queue
N, M, K = map(int, input().split())
F = [[] for _ in range(N+1)]
B = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    B[c].append(d)
    B[d].append(c)

checked = [False] * (N+1)
checked[0] = True
ans = ['0'] * (N+1)
for v in range(1, N+1):
    if checked[v]:
        continue
    A = []
    q = Queue()
    for u in F[v]:
        q.put(u)

    while not q.empty():
        u = q.get()
        if checked[u]: continue
        A.append(u)
        for w in F[u]:
            q.put(w)
        checked[u] = True
    
    for a in A:
        ans[a] = str(len(A)-len(F[a])-1 - len(set(A)&set(B[a])))
    
    checked[v] = True

print(' '.join(ans[1:]))

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

N, M, K = map(int, input().split())
uf = UnionFind(N+1)
F = [0] * (N+1)
B = [0] * (N+1)
for _ in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)
    F[a] += 1
    F[b] += 1

for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(1, N+1):
    ans = uf.size(i) - F[i] - B[i] - 1
    print(ans, end=' ')

print()
### BUGGY CODE ###

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]

  results = [str(A.count(i)) for i in range(1, N+1)]

  print('\n'.join(results))

if __name__ == "__main__":
  resolve()


### FIXED CODE ###

from collections import Counter

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  collection = Counter(A)
  for i in range(1, N + 1):
    print(collection[i])
  # results = [str(A.count(i))+'\n' for i in range(1, N+1)]
  # print('\n'.join(results))

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

n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  for i in range(len(eld)):
    if c in eld[i]:
      index = i
      size = len(eld[i])
      return(index,size)
    
eld = []
for i in range(n):
  eld.append([i])
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    del eld[b_index]
  else:
    eld[b_index].extend(eld[a_index])
    del eld[a_index]
    
  eld_len = len(eld)
  num = 0
  for i in range(eld_len):
    num += len(eld[i]) * (n-len(eld[i]))
  num = int(num/2)
  ans.append(num)

for i in ans[::-1]:
  print(i)


  

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  if c in eld[c]:
    return(c,len(eld[c]))
  else:
    return(eld[c][0],len(eld[eld[c][0]]))
           
eld = []
for i in range(n):
  eld.append([i])
stat = eld
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
#  print(eld)
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
#  print(a_index,b_index)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  else:
    next = a_size * b_size
    ans.append(ans[-1] - next)

  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    for i in eld[b_index]:
      eld[i] = [a_index]
  else:
    eld[b_index].extend(eld[a_index])
    for i in eld[a_index]:
      eld[i] = [b_index]

for i in ans[::-1]:
  print(i)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = list(set(A))
ans = 0
for i in B:
    if A.count(i) % 2 == 1:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
a = A[0]
n = 0
if N == 1:
    print(1)
    sys.exit()
for i in range(N):
    if a == A[i]:
        n += 1
    else:
        if n % 2 == 1:
            ans += 1
        n = 1
        a = A[i]
    #print(A[i],"1",n,n%2,ans)
if A[-1] == A[-2] and n % 2 == 1:
    ans += 1
elif A[-1] != A[-2] and n % 2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for i in p:
    for j in c:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])

### 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)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for j in c:
    for i in p:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])
### BUGGY CODE ###

n = int(input())
*a, = map(int, input().split())
a.sort()
ans = 0
while n:
    a.pop(0)
    a.pop()
    ans += a.pop()
    n -= 1
print(ans)

### FIXED CODE ###

import collections
n = int(input())
*a, = map(int, input().split())
a.sort()
a = collections.deque(a)
ans = 0
while n:
    a.popleft()
    a.pop()
    ans += a.pop()
    n -= 1
print(ans)
### BUGGY CODE ###

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

for l, r in l_r_list:
    S_lr = S[l - 1:r]
    print(S_lr.count("AC"))

### FIXED CODE ###

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [0]

for i in range(1, N):
    if S[i] == "C" and S[i - 1] == "A":
        AC_accumulation.append(AC_accumulation[-1] + 1)
    else:
        AC_accumulation.append(AC_accumulation[-1])


ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))
### BUGGY CODE ###

#https://atcoder.jp/contests/abc098/tasks/arc098_a
n=int(input())
s=input()

ans=100000000000
for i in range(n):
    count=0
    for j in range(n):
        if i==j:
            continue

        if (i<j)&(s[j]=="E"):
            count+=1
        elif (j<i)&(s[j]=="W"):
            count+=1

    ans=min(ans,count)

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc098/tasks/arc098_a
n=int(input())
s=input()

"""ans=100000000000
for i in range(n):
    count=0
    for j in range(n):
        if i==j:
            continue

        if (i<j)&(s[j]=="E"):
            count+=1
        elif (j<i)&(s[j]=="W"):
            count+=1

    ans=min(ans,count)

print(ans)"""#O(N^2)

count_W=[]
for i in range(n):
    count_W.append(0)

if s[0]=="W":
    count_W[0]=1
else:
    count_W[0]=0

for i in range(1,n):
    if s[i]=="W":
        count_W[i]=count_W[i-1]+1
    else:
        count_W[i]=count_W[i-1]

for i in range(n):
    if i==0:
        ans=(n-1)-(count_W[n-1]-count_W[0])
    else:
        ans=min(ans,count_W[i-1]+(n-1-i)-(count_W[n-1]-count_W[i]))

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

n = int(input())
ls = list(map(int,input().split()))
a = 0
for i in range(len(ls)):
    if ls.count(ls[i]) > 1:
        a += 1
        break
    else:
        continue
if a > 0:
    print("NO")
else:
    print("YES")


### FIXED CODE ###

import collections
n = int(input())
ls = list(map(int,input().split()))
if len(ls) == len(collections.Counter(ls)):
    print("YES")
else:
    print("NO")
### 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()))
sumAB=[0 for _ in range(x*y)]
index=0
imax=min(k,x)
jmax=min(k,y)
for i in range(imax):
    for j in range(jmax):
        sumAB[index]=a[i]+b[j]
        index+=1
sumAB.sort(key=lambda x:-x)
c.sort(key=lambda x:-x)
beauty=[0 for _ in range(k*k)]
index=0
imax=min(k,x*y)
jmax=min(k,z)
for i in range(imax):
    for j in range(jmax):
        beauty[index]=sumAB[i]+c[j]
        index+=1
beauty.sort(key=lambda x:-x)
for i in range(k):
    print(beauty[i])

### 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(key=lambda x:-x)
b.sort(key=lambda x:-x)
c.sort(key=lambda x:-x)
beauty=[]
index=0
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1)*(j+1)*(l+1)<=k:
                beauty.append(a[i]+b[j]+c[l])
            else:
                break
beauty.sort(key=lambda x:-x)
for i in range(k):
    print(beauty[i])
### BUGGY CODE ###

N, C = map(int, input().split())
programs = [[0 for _ in range(C)] for _ in range(2*10**5)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(2*s-1, 2*t):
        programs[i][c-1] = 1
ret = 0
for i in range(2*10**5):
    ret = max(ret, sum(programs[i]))
print(ret)


### FIXED CODE ###

N, C = map(int, input().split())
programs = [[0 for _ in range(C)] for _ in range(10**5)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s-1, t):
        programs[i][c-1] = 1
ret = 0
for i in range(10**5):
    ret = max(ret, sum(programs[i]))
print(ret)
### BUGGY CODE ###

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()
A = [0] * N
for i, s in enumerate(S):
    if s == 'G':
        A[i] = 1
    elif s == 'B':
        A[i] = 2

acc = list2d(3, N, 0)
for i, a in enumerate(A):
    acc[a][i] = 1
for i in range(3):
    acc[i] = list(accumulate(acc[i][::-1]))[::-1]

ans = 0
for i, a1 in enumerate(A):
    for j in range(i+1, N):
        a2 = A[j]
        if a1 == a2:
            continue
        a3 = 3 - a1 - a2
        cnt = acc[a3][j]
        dist = j - i
        if j + dist < N and A[j+dist] == a3:
            cnt -= 1
        ans += cnt
print(ans)


### FIXED CODE ###

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()
A = [0] * N
for i, s in enumerate(S):
    if s == 'G':
        A[i] = 1
    elif s == 'B':
        A[i] = 2

acc = list2d(3, N, 0)
for i, a in enumerate(A):
    acc[a][i] = 1
for i in range(3):
    acc[i] = list(accumulate(acc[i][::-1]))[::-1]

ans = 0
for i, a1 in enumerate(A):
    for j in range(i+1, N):
        a2 = A[j]
        if a1 == a2:
            continue
        a3 = 3 - a1 - a2
        cnt = acc[a3][j]
        dist = j - i
        if j + dist < N and A[j+dist] == a3:
            cnt -= 1
        ans += cnt
print(ans)
### BUGGY CODE ###

n = int(input())

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

ans_list = []

for i in range(n):
  ans = 0
  for j in range(i, i + n):
    ans += dams[j % n] * (-1)**(j - i)
  ans_list.append(str(ans))
    
print(" ".join(ans_list))

### FIXED CODE ###

n = int(input())

dams = list(map(int, input().split()))
ans_list = [0 for x in range(n)]

ans_list[0] = sum([dams[x]*(-1)**x for x in range(n)])

for i in range(1, n):
  ans_list[i] = -ans_list[i-1] + 2 * dams[i - 1]

print(" ".join(list(map(str, ans_list))))

#print(*ans_list)
### BUGGY CODE ###

class M_Kun:
    def __init__(self):
        self.money = 1000
        self.stock = 0
        
    def buy(self, value):
        num = 0
        while value * (num+1) <= self.money:
            num += 1
        self.money -= value * num
        self.stock += num
        
    def sell(self, value):
        self.money += value * self.stock
        self.stock = 0

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


local_min = [False]*N
local_max = [False]*N

is_ascending = False
for a in A[1:]:
    if a > A[0]:
        is_ascending = True
        break
    elif a < A[0]:
        break

if is_ascending:
    local_min[0] = True
else:
    local_max[0] = True

for i in range(N-1):
    if A[i] == A[i+1]:
        continue
    elif is_ascending and A[i] > A[i+1]:
        local_max[i] = True
        is_ascending = False
    elif (not is_ascending) and A[i] < A[i+1]:
        local_min[i] = True
        is_ascending = True
        
if is_ascending:
    local_max[-1] = True
    

m_kun = M_Kun()

for i in range(N):
    if local_min[i]:
        m_kun.buy(A[i])
    if local_max[i]:
        m_kun.sell(A[i])
        
print(m_kun.money)        

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline()[:-1]

class M_Kun:
    def __init__(self):
        self.money = 1000
        self.stock = 0
        
    def buy(self, value):
        num = self.money // value
        self.money -= value * num
        self.stock += num
        
    def sell(self, value):
        self.money += value * self.stock
        self.stock = 0


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

    local_min = [False]*N
    local_max = [False]*N

    is_ascending = False
    for a in A[1:]:
        if a > A[0]:
            is_ascending = True
            break
        elif a < A[0]:
            break

    if is_ascending:
        local_min[0] = True
    else:
        local_max[0] = True

    for i in range(N-1):
        if A[i] == A[i+1]:
            continue
        elif is_ascending and A[i] > A[i+1]:
            local_max[i] = True
            is_ascending = False
        elif (not is_ascending) and A[i] < A[i+1]:
            local_min[i] = True
            is_ascending = True

    if is_ascending:
        local_max[-1] = True


    m_kun = M_Kun()

    for i in range(N):
        if local_min[i]:
            m_kun.buy(A[i])
        if local_max[i]:
            m_kun.sell(A[i])

    print(m_kun.money)
    
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)
    exit()
print(ans)

### FIXED CODE ###

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

x=int(input())
a=32
b=0
while x < a**5:
    a=a//2
while a**5 < x:
    a+=1
a-=1
while a**5 - b**5 != x and a**5 + b**5 != x:
    b+=1
if a**5 - b**5 == x:
    print(a,b)
else:
    print(a,b*-1)

### FIXED CODE ###

x = int(input())
for a in range(1001):
    for b in range(1001):
        if (a**5)-(b**5)==x:
            print(a,b)
            exit()
        if (a**5)+(b**5)==x:
            print(a,-1*b)
            exit()
        if (b**5)-(a**5)==x:
            print(-1*a,-1*b)
            exit()
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
N = int(input())
A = tuple(map(int, input().split()))

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

for i in range(N):
    ans += (lcm * inv_t[A[i]])
    ans %= mod

print(ans)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

lcm %= mod
for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

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

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

ans = 1
for i in range(1,N):
  pi = P[i]
  pm = min(P[:i])
  if pi <= pm:
    ans +=1

print(ans)

### FIXED CODE ###

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

ans = 0
m_P = P[0]
for i in range(N):
  if P[i] <= m_P:
    ans += 1
    m_P = P[i]
print(ans)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  for i in range(t):
    A[i] = c
  if t == b:
    A = A[b:d] + A[:b] + A[d:]
print(sum(A))

### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
A = [(1, i) for i in map(int, input().split())]
BC = [ tuple(map(int, input().split())) for _ in range(m) ]
XY = sorted(A + BC, reverse=True, key=itemgetter(1))
c = n
now = 0
ans = 0
while c > 0 and now < n+m:
  x, y = XY[now]
  t = min(c, x)
  ans += y*t
  c -= t
  now += 1
print(ans)