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

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = [list(map(int, input().split())) for _ in range(m)]

import bisect
for i in range(m):
  mid = bisect.bisect_left(a, bc[i][1])
  t = min(mid, bc[i][0])
  for j in range(t):
    a[j] = bc[i][1]
  a.sort()
  
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cb=[]
for i in range(m):
    b, c = map(int, input().split())
    cb.append([c,b])
cb.sort(reverse=True)
k=0
for i in range(m):
    j=0
    while j<cb[i][1] and k+j<n and a[k+j]<cb[i][0]:
        a[k+j] = cb[i][0]
        j+=1
    k+=j
    if k==n:
        break
print(sum(a))
### BUGGY CODE ###

n,m  = map(int,input().split())
a = [int(x) for x in input().split()]

ans1 = [1]
temp = 0
count = 0
while(True):
    ans1 += [a[temp]]
    temp = a[temp]-1
    if len(ans1) !=  len(set(ans1)):
        break
    count += 1
    if count == m:
        print(ans1[len(ans1)-1])
        exit()

num1 = ans1.index(temp+1)
ans2 = ans1[num1:len(ans1)-1]

num = len(ans2)

print(ans2[(m-num1)%num])


### FIXED CODE ###

n,m  = map(int,input().split())
a = [int(x) for x in input().split()]

ans1 = [1]
temp = 0
visit = [0]*(n+1)
visit[1] = 1
while(True):
    ans1 += [a[temp]]

    if visit[a[temp]] == 1:
        break

    visit[a[temp]] = 1
    temp = a[temp]-1


    if len(ans1) == m+1:
        print(ans1[len(ans1)-1])
        exit()


num1 = ans1.index(a[temp])
ans2 = ans1[num1:len(ans1)-1]

num = len(ans2)

print(ans2[(m-num1)%num])
### BUGGY CODE ###

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

### FIXED CODE ###

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

# coding: utf-8
import math
import collections


def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for tmp in inputs:
        if int(tmp[0]) - int(tmp[1]) < 0:
            for i in range(0, int(tmp[0]) + int(tmp[1])):
                inputs_list.append(i)
        else:
            for i in range(int(tmp[0]) - int(tmp[1]), int(tmp[0]) + int(tmp[1])):
                inputs_list.append(i)

    c = collections.Counter(inputs_list)
    print(n - (c.most_common()[0][1] - 1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for i in inputs:
        if int(i[0]) - int(i[1]) < 0:
            inputs_list.append([0, int(i[0]) + int(i[1])])
        else:
            inputs_list.append([int(i[0]) - int(i[1]), int(i[0]) + int(i[1])])
    sorted_data = sorted(inputs_list, key=lambda x: (x[1]))

    ans = [sorted_data[0]]
    cur = ans[0][1]
    for i in range(len(sorted_data) - 1):
        if cur <= sorted_data[i + 1][0]:
                ans.append(sorted_data[i + 1])
                cur = sorted_data[i + 1][1]
    print(len(ans))


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

#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 1000000007  # type: int

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1
    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
    #pprint(dp)
    ret = dp[N][M] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, S, T)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 1000000007  # type: int

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1
    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
            dp[i + 1][j + 1] %= MOD
    #pprint(dp)
    ret = dp[N][M]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, S, T)

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n = int(input())
cnt = 0
for i in range(1,n):
  d = make_divisors(n-i)
  cnt += len(d)
print(cnt)

    

### FIXED CODE ###

n = int(input())
cnt = 0
for i in range(1,n):
  cnt += (n-1)//i
print(cnt)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for q in range(Q):
  l, r = map(int, input().split())
  si = S[l-1:r].replace("AC","11")
  si = si.translate(str.maketrans({"A":"0","T":"0","G":"0","C":"0"}))
  print(int(sum(map(int,list(si)))/2))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
c = [0]
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    c.append(c[-1]+1)
  else:
    c.append(c[-1])
    
for i in range(q):
  l, r = map(int, input().split())
  print(c[r-1] - c[l-1])
### BUGGY CODE ###

H,N=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(N)]
ab.sort()

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    for a,b in ab:
        if a+i>H:
            a=H-i
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
    i+=1

print(ans[H])

### FIXED CODE ###

H,N=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(N)]
ab.sort()

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    for a,b in ab:
        if a+i>H:
            a=H-i
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
    i+=1

print(ans[H])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
  if sum(a[i:i+k]) < sum(a[i+1:i+k+1]):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n - k):
  if a[i] < a[i + k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import defaultdict

#素因数分解O(√n)
def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res

N = int(input())

ans = 0
for i in range(1, N+1):
    d = primeFactor(i)
    if d == {}:
        p = 1
    else:
        p = 1
        for v in d.values():
            p *= (v+1)
    ans += i*p

print(ans)


### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1, N+1):
    p = N // i
    ans += i * (p*(p+1)//2)

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

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1;d=[a[0]]
while (not b==2) and (len(set(d))==len(d)):
  b=a[b-1]
  c+=1
  d.append(b)
if b==2:print(c)
else:print(-1)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1
while b!=2 and c<=n:
  b=a[b-1]
  c+=1
if b==2:print(c)
else:print(-1)
### BUGGY CODE ###

n,total = map(int,input().split())

a = b = c = -1

for i in range(0,n+1):
    for j in range(0,n+1):
        x = i
        y = j
        z = n - i - j
        if n >= x >=0 and n >= y >=0 and n >= z >=0:
            sum = 10000*int(x) + 5000*int(y) + 1000*int(z) 
            if total == sum:
                a = x
                b = y
                c = z
                break
        
print(a,b,c)            
        
            

### FIXED CODE ###

n,total = map(int,input().split())

a = b = c = -1

for i in range(0,n+1):
    x = i
    for j in range(0,n+1-x):
        
        y = j
        z = n - i - j
        if n >= x >=0 and n >= y >=0 and n >= z >=0:
            if total == 10000*int(x) + 5000*int(y) + 1000*int(z):
                a = x
                b = y
                c = z
                break
            else:
                continue
            break
print(a,b,c)
### BUGGY CODE ###

N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

### FIXED CODE ###

N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)
### BUGGY CODE ###

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


def main():    
    MOD = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    ans = 0
    for i in range(60):
        x = 0
        for j in range(n):
            if a[j] >> i & 1:
                x += 1
        ans += x * (n - x) * 2 ** i
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1:
            x += 1
    ans += x * (n - x) * 2 ** i
    ans %= MOD
print(ans)
### BUGGY CODE ###

n,*p=map(int,open(0).read().split())
flg=True
cnt=0
for i in range(n):
  flg=True
  for j in range(i):
    if p[i]>p[j]:
      flg=False
  if flg:
    cnt+=1   
print(cnt)  


### FIXED CODE ###

n,*p=map(int,open(0).read().split())
_min=max(p)
cnt=0
for i in p:
  _min=min(_min,i)
  if i>_min:
    cnt+=1
print(n-cnt)
### BUGGY CODE ###

S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    Q_0 = int(3**(bQ + aQ))
    if(Q_0 == 1):
        Q_1 = 0
        Q_2 = 0
    elif(Q_0 == 3):
        Q_1 = 1
        Q_2 = 0
    else:
        Q_1 = Q_0 // 3
        Q_2 = Q_1 // 3
    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)
    ans = ans % max_S

print(ans)

### FIXED CODE ###

S = input()

d = [0, 0, 0, 1]

max_ans = 10**9 + 7

for c in reversed(S):
    # print(c, d)
    m = [c == "A", c == "B", c == "C", c == "?"]
    if(m[3] is True):
        tmp = 3
    else:
        tmp = 1

    for j in range(3):
        d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
    d[3] = (tmp * d[3]) % max_ans

print(d[0])
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=998244353
ans=0
import math

  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
com=math.factorial(n-1)//(math.factorial(n-kk)*math.factorial(kk-1))
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(com%mod)%mod
  com=com*(n-kk)//kk
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)
  

### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
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 = 998244353 #出力の制限
N = 2*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 )


  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(cmb((n-1),(n-kk),mod))%mod
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)
### BUGGY CODE ###

a,b,c,d,e,f=map(int,input().split())
ans=[]
for i in range(30):
  for j in range(30):
    if i*a*100+j*b*100<=f:
      for p in range(3000):
        for q in range(3000):
          if p*c+q*d<=(i*a+j*b)*e and (p*c+q*d+i*a*100+j*b*100<=f):
            ans.append([p*c+q*d+i*a*100+j*b*100,p*c+q*d])
stack=0
index=0
for i in ans:
  if stack<i[0]/i[1]:
    stack=i[0]/i[1]
    index=i
if index==0:
  print(0,0)
else:
  print(ans[index])

### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
dp=[-1]*(f+1)
dp[0]=0
flag=True
for i in range(1,f+1):
  for j in [a*100,b*100]:
    if i-j>=0 and dp[i-j]!=-1:
      dp[i]=max(0,dp[i])
  for j in [c,d]:
    if i-j>=0 and dp[i-j]!=-1:
      if 100*(dp[i-j]+j)<=e*(i-(dp[i-j]+j)):
        dp[i]=max(dp[i],dp[i-j]+j)
      else:
        for k in [a*100,b*100]:
          if i-k-j>=0 and dp[i-k-j]!=-1:
            if 100*(dp[i-k-j]+j)<=e*(i-(dp[i-k-j]+j)):
              dp[i]=max(dp[i],dp[i-k-j]+j)
stack=0
index=min(a*100,b*100)
for i in range(index+1,f+1):
  if dp[i]>0:
    if stack<(dp[i]*100)/i:
      stack=(dp[i]*100)/i
      index=i
print(index,dp[index])
### BUGGY CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


ans = 0


def main():
    N, S = geta(int)
    A = list(geta(int))
    mod = 998244353

    def dfs(n, s, ret):

        global ans

        if s == 0:
            ans = (ans + pow(2, N - ret)) % mod
            return
        if n == 0:
            return

        if sum(A[:n]) < s:
            return

        dfs(n - 1, s - A[n - 1], ret + 1)

        dfs(n - 1, s, ret)

    dfs(N, S, 0)

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

    dp = [[0] * (S + 1) for _ in range(N + 1)]
    for s in range(S + 1):
        dp[0][s] = 0

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

    for i in range(1, N + 1):
        for j in range(1, S + 1):
            if j >= A[i - 1]:
                dp[i][j] = dp[i - 1][j - A[i - 1]] * inv2 + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

            dp[i][j] %= mod

    print(dp[N][S])


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

N, K = map(int, input().split())
nlist = list(map(int, input().split()))
maximum = 0
for l in range(N-K+1):
  maximum = max(maximum, sum(i for i in nlist[l:l+K]))
print((maximum+K)/2)


### FIXED CODE ###

N, K = map(int, input().split())
nlist = list(map(int, input().split()))
Ktot = sum(i for i in nlist[:K])
maximum = Ktot
for l in range(N-K):
  Ktot = Ktot - nlist[l] + nlist[l+K]
  maximum = max(maximum, Ktot)
print((maximum+K)/2)
### BUGGY CODE ###

def main():
    K = int(input())
    if K%2 == 0:
        return -1
    i = 0
    amari_sum = 0
    i = 1
    amari = 7 % K
    amari_sum += amari
    if amari == 0:
        return i

    while True:
        i += 1
        amari = (amari*10) % K
        amari_sum += amari
        if amari_sum % K == 0:
            return i
        else:
            amari_sum %= K

print(main())


### FIXED CODE ###

def main():
    K = int(input())
    if K%2 == 0:
        return -1
    ans = 1
    amari_reserve = 7%K
    amari = amari_reserve
    if amari_reserve == 0:
        return ans

    while (ans <= K):
        ans += 1
        amari = (10*amari+7) % K
        if amari == 0:
            return ans
        if amari == amari_reserve:
            return -1

    return -1


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

# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
ans =1
for i in A:
    ans *=i
if ans <=10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
ans =1
if 0 in A:
    ans =0
else:
    for i in A:
        ans *=i
        if 10**18 < ans :
            ans = -1
            break
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
import re
for l, r in lr:
    s_ = s[l - 1 : r]
    ans = len(re.findall('AC', s_))
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ac_sum = [0] * (N + 1)
s = list(s)
i = 0
while i < N:
    if s[i : i + 2] == ['A', 'C']:
        #print(i)
        ac_sum[i + 2] += ac_sum[i] + 1
        ac_sum[i + 1] += ac_sum[i] + 1
        i += 2
    else:
        ac_sum[i + 1] = ac_sum[i]
        i += 1
for l, r in lr:
    l -= 1
    r -= 1
    print(ac_sum[r] - ac_sum[l])
### BUGGY CODE ###

# 2019/05/12
# diverta 2019 Programming Contest - B

# Input
r, g, b, n = map(int, input().split())

cnt = 0
for i in range(n+1):
    
    rcnt = r * i
    if rcnt > n:
        break
    
    for j in range(n+1):
        gcnt = g * j
        rgcnt = rcnt + gcnt
        if rgcnt > n:
            break

        bcnt = n - rgcnt
        if bcnt % b == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

# 2019/05/12
# diverta 2019 Programming Contest - B

# Input
r, g, b, n = map(int, input().split())

# Init
cnt = 0

# Calc
for i in range(n+1):
    rcnt = r * i
    if rcnt > n:
        break
    
    for j in range(n+1):
        rgcnt = rcnt + g * j
        if rgcnt > n:
            break
        bcnt = n - rgcnt
        if bcnt % b == 0:
            cnt += 1
# Output
print(cnt)
### BUGGY CODE ###

[N,K]=[int(x) for x in input().split()]
h=[int(x) for x in input().split()]

dp=[0 for i in range(N)]

for i in range(N):
  for j in range(1,K+1):
    if j==1 and N-1+j-i<=N-1:
      dp[N-1-i]=dp[N-i]+abs(h[N-i-1]-h[N-i])
    elif N-1-i+j<=N-1:
      dp[N-i-1]=min(dp[N-i-1+j]+abs(h[N-i-1]-h[N-1-i+j]),dp[N-i-1])
print(dp[0])

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
[N,K]=[int(x) for x in input().split()]
h=[int(x) for x in input().split()]
h=np.array(h)
dp=np.zeros(N,dtype=int)
 
for i in range(1,N):
  last=min(K,i)+N-i
  dp[N-i-1]=min(dp[N-i:last]+np.abs(h[N-i:last]-h[N-i-1]))
print(dp[0])
### BUGGY CODE ###

def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x: str) -> int:
		s = str(x)
		ans = 0
		for i in A:
			a, b, c, d = i[0], i[1], i[2], i[3]
			if int(s[b-1]) - int(s[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = str(q.popleft())
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)
resolve()

### FIXED CODE ###

from collections import deque


# 数列の点数を計算する関数
def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b - 1] - seq[a - 1] == c:
            score += d

    return score


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

ans = 0

que = deque()

# 数列の1番目、[1]～[m]までキューに追加しますが、
# 実は、この問題は数列の最初が[1]の場合だけを考えても解けます。
for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.popleft()

    if len(seq) == n:
        # 長さがnになったので、得点を計算します
        score = calc(seq)
        ans = max(ans, score)
    else:
        # 次に追加する数字は、下限が今の数列の一番後ろの数字、上限がmです
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)

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


def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1%v2)

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

MOD = 10**9 + 7

a_lcm = a_list[0]
for a in a_list[1:]:
    a_lcm *= a // gcd(a_lcm, a)

res = 0
for a in a_list:
    res = (res + a_lcm // a) % MOD
print(res)


### FIXED CODE ###


from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

if __name__ == "__main__":
    main()