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

H, N = list(map(int, input().split()))
AB = [[None,None]]
for i in range(N):
  AB.append(list(map(int, input().split())))

dp = [[int(1e8) for i in range(H+1)] for j in range(N+1)] 
for n in range(N+1):
  dp[n][0] = 0

for n in range(1,N+1):
  for h in range(1,H+1):
    ionly_n = int(h/AB[n][0]) + 1
    cand = [dp[n-1][h-i_n*AB[n][0]] + AB[n][1] * i_n for i_n in range(ionly_n)] + [AB[n][1] * ionly_n]
    dp[n][h] = min(cand)
#print(dp)
print(dp[N][H])

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

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

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

ans = 1
for i in range(N):
  ans = ans * a[i]

if (ans > 10**18):
  print('-1')
else:
  print(ans)


### FIXED CODE ###

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

ans = 1
for i in range(N):
  ans = ans * a[i]
  if (ans > 10 ** 18):
    break
  
if (ans > 10**18):
  if a.count(0) > 0:
    print(0)
  else:
    print(-1)
else:
  print(ans)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
def cmb(n,r):
    return factorial(n) // factorial(r) // factorial(n - r)

n=ii()
arr=limii()

cou=Counter(arr)
ans=0
for i,j in cou.items():
    if j>=2:
        ans+=cmb(j,2)

for i in arr:
    if cou[i]>2:
        a=0
        print(ans-cmb(cou[i],2)+cmb(cou[i]-1,2))
    elif cou[i]==2:
        print(ans-1)
    else:
        print(ans)







### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter,mul
from fractions import gcd
from functools import reduce
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n=ii()
arr=limii()

cou=Counter(arr)
ans=0
for j in cou.values():
    if j>=2:
        ans+=cmb(j,2)

for i in arr:
    if cou[i]>2:
        print(ans-cmb(cou[i],2)+cmb(cou[i]-1,2))
    elif cou[i]==2:
        print(ans-1)
    else:
        print(ans)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    from functools import reduce
    def Comb(N, A):
        num = reduce(lambda x, y: x * y, range(N, N-A, -1))
        den = reduce(lambda x, y: x * y, range(1, A+1))
        return num//den
    ans = lp[0]
    for i in range(P):
        ans += Comb(lp[i], 2)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.append(0)
i = 0
while i<N:
    print(A.count(i+1))
    i+=1

### FIXED CODE ###

import collections
 
N = int(input())
A = list(map(int, input().split()))
 
c = collections.Counter(A)
 
for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
c = 0
for i in range(1,N+1):
    P_ = P[:i]
    pi = P[i-1]
    if min(P_) >= pi:
        c += 1
    # print(P_,pi)
print(c)


### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
c = 0
mi = P[0]
for i in range(N):
    if P[i] < mi:
        mi = P[i]
        c += 1
    # print(mi)
print(c+1)
### BUGGY CODE ###

from itertools import combinations

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

an = sorted(an,reverse=True)
if K in an:
    print('POSSIBLE')
    exit()

visited = {}
def dfs(a, b):
    d = a - b 
    if K == d:
        return 1
    if d in an:
        return 0
    visited[(a,b)]=True
    for it in combinations(an + [d], 2):
        if visited.get((it[0],it[1]), False):
            continue
        if dfs(it[0], it[1]) == 1:
            return 1
    return 0
        
comb=combinations(an, 2)
s=sum([dfs(it[0], it[1]) for it in comb])
if s == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

### FIXED CODE ###

from functools import reduce
from fractions import gcd

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

m = max(an)
g = reduce(lambda x, y: gcd(x, y), an)

if K <=m and K % g == 0:
    print ('POSSIBLE')
else:
    print ('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
li_a = list()
d_a = dict()

for _ in range(n):
    wk = int(input())
    li_a.append(wk)

    get = d_a.get(wk, 0)
    d_a[wk] = get + 1

for i in range(n):
    print(max(k for k, v in d_a.items() if not (k == li_a[i] and v == 1)))


### FIXED CODE ###

n = int(input())
li_a = list()
d_a = dict()

for _ in range(n):
    wk = int(input())
    li_a.append(wk)

    get = d_a.get(wk, 0)
    d_a[wk] = get + 1

li_top2 = sorted(d_a.keys(), reverse=True)[:2]

for i in range(n):
    val = li_a[i]

    if val not in li_top2:
        print(li_top2[0])
    else:
        if val == li_top2[0] and d_a.get(val, 0) == 1:
            print(li_top2[1])
        else:
            print(li_top2[0])
### BUGGY CODE ###

import copy


def sumPrice(N, B):
    sum = 0
    for i in range(1, N):
        sum += abs(B[i] - B[i - 1])
    sum += abs(B[N-1] - B[0])
    return sum


N = int(input())
A = []
A = [int(i) for i in input().split()]
A.insert(0, 0)
for i in range(1, N + 1):
    B = copy.deepcopy(A)
    del B[i]
    print(sumPrice(N, B))


### FIXED CODE ###

import copy

"""
def sumPrice(N, B):
    sum = 0
    for i in range(1, N):
        sum += abs(B[i] - B[i - 1])
    sum += abs(B[N-1] - B[0])
    return sum


N = int(input())
A = []
A = [int(i) for i in input().split()]
A.insert(0, 0)
for i in range(1, N + 1):
    B = copy.deepcopy(A)
    del B[i]
    print(sumPrice(N, B))
"""
N = int(input())
A = []
A = [int(i) for i in input().split()]
A.insert(0, 0)
A.insert(N+1, 0)

defSumPrice = 0
for i in range(1, N + 2):
    defSumPrice += abs(A[i - 1] - A[i])

for i in range(1, N + 1):  # A[i] に行かない
    sumPrice = 0
    if (A[i - 1] < A[i] and A[i+1] < A[i])or(A[i - 1] > A[i] and A[i+1] > A[i]):
        if abs(A[i] - A[i - 1]) > abs(A[i] - A[i + 1]):
            sumPrice = defSumPrice - 2 * abs(A[i] - A[i + 1])
        else:
            sumPrice = defSumPrice-2*abs(A[i]-A[i-1])
    else:
        sumPrice = defSumPrice
    print(sumPrice)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    flg=False
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
        else:
            flg=True
    if flg:
        for dy,dx in [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1),(-2,0),(2,0),(-2,1),(-1,1),(1,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]:
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.':
                if (ny,nx) not in d and (ny-1,nx) not in d and (ny,nx-1) not in d and (ny+1,nx) not in d and (ny+1,nx) not in d:
                    q.append((ny,nx))
                    d[(ny,nx)]=d[(y,x)]+1
                elif (ny,nx) in d and d[(ny,nx)]>d[(y,x)]+1:
                    q.append((ny,nx))
                    d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-1)

### FIXED CODE ###

from collections import deque
INF=10**10
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
d=[[INF]*W for _ in range(H)]
d[s[0]][s[1]]=0
q=deque()
q.append(s)
while q:
    y,x=q.pop()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.' and d[ny][nx]>d[y][x]:
            q.append((ny,nx))
            d[ny][nx]=d[y][x]
    for dy in range(-2,3):
        for dx in range(-2,3):
            if abs(dy)+abs(dx)<=1:
                continue
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and d[ny][nx]>d[y][x]+1:
                q.appendleft((ny,nx))
                d[ny][nx]=d[y][x]+1
ans=d[g[0]][g[1]]
if ans<INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

s = list(input())
x, y = map(int, input().split())

z = [0]
for i in s:
    if i=='F':
        z[-1] += 1
    else:
        z.append(0)
_y = len(z)//2
_x = len(z) - _y
len_s = len(s)
dp_x = [0 for _i in range((2*len_s+2))]
dp_x_to = [0 for _i in range((2*len_s+2))]
dp_y = [0 for _i in range((2*len_s+2))]
dp_y_to = [0 for _i in range((2*len_s+2))]

dp_x[z[0]] = 1
dp_y[0] = 1

for i in range(1, len(z)):
    if i%2==0:
        for j in range(-len_s, len_s+1):
            dp_x_to[j] = max(
                dp_x[j-z[i]],
                dp_x[j+z[i]]
            )
        dp_x = dp_x_to.copy()
    else:
        for j in range(-len_s, len_s+1):
            dp_y_to[j] = max(
                dp_y[j-z[i]],
                dp_y[j+z[i]]
            )
        dp_y = dp_y_to.copy()

if dp_x[x] == dp_y[y] == 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = list(input())
x, y = map(int, input().split())

z = [0]
for i in s:
    if i=='F':
        z[-1] += 1
    else:
        z.append(0)
_y = len(z)//2
_x = len(z) - _y
len_s = len(s)
dp_x = [0 for _i in range((2*len_s+2))]
dp_x_to = [0 for _i in range((2*len_s+2))]
dp_y = [0 for _i in range((2*len_s+2))]
dp_y_to = [0 for _i in range((2*len_s+2))]

dp_x[z[0]] = 1
dp_y[0] = 1

for i in range(1, len(z)):
    if i%2==0:
        for j in range(-len_s, len_s+1):
            dp_x_to[j] = max(
                dp_x[j-z[i]],
                dp_x[j+z[i]]
            )
        dp_x = dp_x_to.copy()
    else:
        for j in range(-len_s, len_s+1):
            dp_y_to[j] = max(
                dp_y[j-z[i]],
                dp_y[j+z[i]]
            )
        dp_y = dp_y_to.copy()

if dp_x[x] == dp_y[y] == 1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def solve():
    MOD = 10**9 + 7

    Ss = input()

    N = len(Ss)

    dp = [0] * 13
    dp[0] = 1
    for d, Sd in enumerate(Ss):
        dp2 = [0] * 13
        for mod13 in range(13):
            if Sd != '?':
                x = int(Sd)
                mod13n = (10*mod13 + x) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n] %= MOD
            else:
                for x in range(10):
                    mod13n = (10*mod13 + x) % 13
                    dp2[mod13n] += dp[mod13]
                    dp2[mod13n] %= MOD
        dp = dp2

    print(dp[5])


solve()


### FIXED CODE ###

MOD = 10**9 + 7

Ss = input()

N = len(Ss)

dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
for d, Sd in enumerate(Ss):
#    print(d, Sd)
    for mod13 in range(13):
        if Sd != '?':
            x = int(Sd)
            mod13n = (10*mod13 + x) % 13
            dp[d+1][mod13n] += dp[d][mod13]
            dp[d+1][mod13n] %= MOD
        else:
            for x in range(10):
                mod13n = (10*mod13 + x) % 13
                dp[d+1][mod13n] += dp[d][mod13]
                dp[d+1][mod13n] %= MOD

print(dp[-1][5])
### BUGGY CODE ###

import collections

N, K = map(int, input().split())
A = map(int, input().split())
counter = 0
collection = collections.Counter(A)
k = len(collection)
if k > K:
  change_n = k -K
  for i in range(change_n):
    min_k = collection.most_common()[-1-i][1]
    counter += min_k

print(counter)

### FIXED CODE ###

N, K = map(int, input().split())
A = map(int, input().split())
counter = 0
dic = {}

for a in A:
  if a in dic.keys():
    dic[a] += 1
  else:
    dic[a] = 1

k = len(dic)
v = sorted(dic.values())
if k > K:
  change_n = k -K
  for i in range(change_n):
    min_k = v[i]
    counter += min_k

print(counter)
### BUGGY CODE ###

x, y = map(int, raw_input().split())
for i in xrange(x, x*y, x):
    if not i % y == 0:
        print i
        break
else:
    print -1


### FIXED CODE ###

import sys
x, y = map(int, raw_input().split())
if x == y:
    print -1
    sys.exit()
for i in xrange(x, x*y, x):
    if not i % y == 0:
        print i
        break
else:
    print -1
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
s = 0
for i in range(n-1,1,-1):
  a = l[i]
  for j in range(i-1,0,-1):
    b = l[j]
    for k in range(0,j):
      c = l[k]
      if(b+c>a):
        s += j-k
        break
print(s)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
s = 0
for i in range(0,n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    s += bisect.bisect_left(l,a+b,j+1)-j-1
print(s)
### BUGGY CODE ###

N, W = map(int, input().split())

WV = [tuple(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
R = N * 3

dp = [[-10**18] * (R + 1) for _ in range(N + 1)]
dp[0][0] = 0

for w, v in WV:
    w -= W0
    for n in range(N)[::-1]:
        for i in range(R)[::-1]:
            if i + w <= R:
                dp[n + 1][i + w] = max(dp[n + 1][i + w], dp[n][i] + v)

ans = 0
for n in range(N + 1):
    for w in range(R + 1):
        if n * W0 + w <= W:
            ans = max(ans, dp[n][w])
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())

items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append((v, w))

w0 = items[0][1]
itemGrp = [[] for _ in range(4)]
for v, w in items:
    itemGrp[w - w0].append(v)

for i in range(4):
    itemGrp[i].sort(reverse=True)

accItemGrp = []
for i in range(4):
    item = itemGrp[i]
    accValue = [0] * (len(item) + 1)
    for i in range(1, len(item) + 1):
        accValue[i] = accValue[i - 1] + item[i - 1]
    accItemGrp.append(accValue)

ans = 0
for n0 in range(len(itemGrp[0]) + 1):
    for n1 in range(len(itemGrp[1]) + 1):
        for n2 in range(len(itemGrp[2]) + 1):
            for n3 in range(len(itemGrp[3]) + 1):
                weight = (n0 + n1 + n2 + n3) * w0 + n1 + 2 * n2 + 3 * n3
                if weight <= W:
                    value = 0
                    for i, n in enumerate([n0, n1, n2, n3]):
                        value += accItemGrp[i][n]
                    ans = max(ans, value)

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

N, M = map(int, input().split())
A_list = list(map(int, input().split()))

A_sorted = sorted(A_list)

CB_list = []
for _ in range(M):
    B, C = map(int, input().split())
    CB_list.append((C, B))
    
CB_reverse_sorted = sorted(CB_list, reverse=True)

pointer = 0

for CB_tuple in CB_reverse_sorted:
    C = CB_tuple[0]
    B = CB_tuple[1]
    
    for i in range(pointer, pointer + B):
        if i >= N:
            continue
            
        if A_sorted[i] < C:
            A_sorted[i] = C
            
    pointer += B

print(sum(A_sorted))

### FIXED CODE ###

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
 
A_sorted = sorted(A_list)
 
CB_list = []
for _ in range(M):
    B, C = map(int, input().split())
    CB_list.append((C, B))
    
CB_reverse_sorted = sorted(CB_list, reverse=True)
 
bflag = False
pointer = 0

for CB_tuple in CB_reverse_sorted:
    C = CB_tuple[0]
    B = CB_tuple[1]
    
    for i in range(pointer, pointer + B):
        if i >= N or A_sorted[i] > C:
            bflag = True
            break
            
        if A_sorted[i] < C:
            A_sorted[i] = C
            
    pointer += B
    
    if bflag == True:
        break

print(sum(A_sorted))
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = [list(readline().decode('utf-8').strip()) for _ in range(H)]
    dist = [[INF] * (W+2) for _ in range(H+2)]
    dxy = ((1, 0), (0, 1), (-1, 0), (0, -1))
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if (y,x) == (gy, gx):
            print(d)
            sys.exit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if dist[n_y][n_x]<d:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

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

import fractions
N = int(input())
list_A = list(map(int, input().split()))
ans = 1
sum = 0
for i in range(N):
    ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
    sum += ans//a
print(sum%(7+10**9))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))