Harryxun/stf_run huggingface dataset:
from sys import stdin
import math

def count_div(a, b, div):
    ac = a // div
    if ac * div < a:
        ac += 1
    bc = b // div
    if bc * div > b:
        bc -= 1
    return bc - ac + 1

if __name__ == '__main__':
    A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]

    nc = count_div(A, B, C)
    
    nd = count_div(A, B, D)
    
    CD = int(C * D / math.gcd(C, D))
    ncd = count_div(A, B, CD)
    
    n = B - A + 1
    
    ans = n - (nc + nd - ncd)
    print(ans)

### FIXED CODE ###

from sys import stdin

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def count_div(a, b, div):
    ac = a // div
    if ac * div < a:
        ac += 1
    bc = b // div
    if bc * div > b:
        bc -= 1
    return bc - ac + 1

if __name__ == '__main__':
    A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]

    nc = count_div(A, B, C)
    
    nd = count_div(A, B, D)
    
    CD = int(C * D / gcd(C, D))
    ncd = count_div(A, B, CD)
    
    n = B - A + 1
    
    ans = n - (nc + nd - ncd)
    print(ans)
N, A, B = map(int, input().split())

items = []
A_MAX = 0
B_MAX = 0
MAX_cost = 0
for _ in range(N):
    a, b, cost = map(int, input().split())
    items.append((a, b, cost))
    A_MAX += a
    B_MAX += b
    MAX_cost += cost

dp = [[float('infinity')] * (A_MAX + 1) for _ in range(B_MAX + 1)]

dp[0][0] = 0
for a, b, cost in items:
    dp[b][a] = cost

for a, b, cost in items:
    for i in range(1, B_MAX + 1):
        for j in range(1, A_MAX + 1):
            if j - a > 0 and i - b > 0:
                dp[i][j] = min(dp[i][j], dp[i - b][j - a] + cost)

ans = float('infinity')
for k in range(1, B_MAX + 1):
    for l in range(1, A_MAX + 1):
        if dp[k][l] == float('infinity'):
            continue
        if A * dp[k] == dp[l] * B:
            ans = min(ans, dp[k][l])
if ans == float('infinity'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys



n, ma, mb = map(int, input().split())
abc = []

for _ in range(n):
    a, b, cost = map(int, input().split())
    abc.append((a, b, cost))

def main():
    sa = 0
    sb = 0
    for i in range(n):
        sa += abc[i][0]
        sb += abc[i][1]

    res = [[float('infinity')] * (sb + 1) for _ in range(sa + 1)]
    res[0][0] = 0

    for a, b, c in abc:

        for j in range(sa, -1, -1):
            for k in range(sb, -1, -1):
                if j >= a and k >= b:
                    res[j][k] = min(res[j][k], res[j-a][k-b] + c)

    ans = float('infinity')
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = min(ans, res[ma*i][mb*i])

    if ans == float('infinity'):
        return -1
    else:
        return ans

if __name__ == '__main__':
    ans = main()
    print(ans)
-1000000000 0 -1000000000 0

### FIXED CODE ###

a,b,c,d = list(map(int,input().split()))

print(max(a*c,a*d,b*c,d*b))
a,b = map(raw_input().split())

if a > b:
  print "a > b"

if a < b:
  print "a < b"

else
 print "a == b"

### FIXED CODE ###

a,b = map(int, raw_input().split())
 
if a > b:
  print 'a > b'
 
elif a < b:
  print 'a < b'
 
else:
  print 'a == b'
import collections
S = input()
cnt = 0

length = len(S)
mod = [0]
reverse_S = S[::-1]
tens = 1
for i in range(len(S)):
  now = int(reverse_S[i])*tens%2019
  mod.append((now+mod[i])%2019)
  tens *= 10
  tens %= 2019;

c = collections.Counter(mod)
hindo = sorted(c.values(),reverse=True)
for i in range(hindo.index(1)):
  n = hindo[i]
  cnt += n*(n-1)/2

print(int(cnt))

### FIXED CODE ###

import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)
number = int(input())
tall = list(map(int, input().split()))
addition = 0
for each in range(1, number + 1):
  difference = tall[each - 1] - tall[each]
  if difference > 0:
    addition += difference
    tall[each] += difference
print(addition)

### FIXED CODE ###

number = int(input())
tall = list(map(int, input().split()))
addition = 0
for each in range(1, number):
    difference = tall[each - 1] - tall[each]
    if difference >= 0:
        addition += difference
        tall[each] += difference
print(addition)
h, w, m = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(m)]
high = [0] * h
weig = [0] * w
for i in range(m):
    high[hw[i][0] - 1] += 1
    weig[hw[i][1] - 1] += 1
m_high = high.index(max(high))
m_weig = weig.index(max(weig))
ans = max(high) + max(weig)
for i, x in enumerate(high) if x == max(high):
    for j, y in enumerate(l_dup) if x == max(weig):
        ans -= 1
print(ans)

### FIXED CODE ###

h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
h_max = max(h_list)
w_max = max(w_list)
w_flag = [0 for _ in range(w)]
for i in range(w):
    if w_list[i] == w_max:
        w_flag[i] = 1
h_flag = [0 for _ in range(h)]
for i in range(h):
    if h_list[i] == h_max:
        h_flag[i] = 1
flag = 0   
for i in range(m):
    if h_flag[a_list[i][0] - 1] == 1 and w_flag[a_list[i][1] - 1] == 1:
        flag += 1
s = sum(h_flag) * sum(w_flag)
print(h_max + w_max - 1 if flag == s else h_max + w_max)
N, X, M = map(int, input().split())

rec = []
s = set()
rec.append(X)
s.add(X)
r = X

for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())

rec = []
s = set()
rec.append(X)
s.add(X)
r = X
idx = -1
idx1 = -1
for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx == -1 or idx1 == -1):
    print(sum(rec[:N]))
elif(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):
    s = 'abcdefghijkl'
    ans = []
    from heapq import heapify, heappop, heappush

    def f(t: str):
        if len(t) == N:
            heappush(ans, t)
            return
        
        if len(t) >= 2:
            x = s.index(max(list(t)))+3
        else:
            x = len(t)+1
        for i in range(x):
            f(t+s[i])


    
    f('')
    # print(ans)
    c = 0
    # print(len(ans))
    while len(ans):
        print(heappop(ans))
        c += 1


    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
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):
    s = 'abcdefghijkl'
    ans = []
    from heapq import heapify, heappop, heappush

    def f(t: str):
        if len(t) == N:
            # heappush(ans, t)
            ans.append(t)
            return
        
        if len(t) >= 2:
            x = s.index(max(list(t)))+2
        else:
            x = len(t)+1
        for i in range(x):
            f(t+s[i])


    
    f('')
    # print(ans)
    c = 0
    # print(len(ans))
    # while len(ans):
    #     print(heappop(ans))
    #     c += 1
    ans.sort()
    for i in ans:
        print(i)


    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
    solve(N)

if __name__ == '__main__':
    main()
while True:
    x=input().split()
    h=int(x[0])
    w=int(x[0])
    if a==0 and b==0:break
    for i in range (h):
        for j in range (w):
        print('#'*w)
    print(" ")


### FIXED CODE ###

while True:
    v=input().split()
    a=int(v[0])
    b=int(v[1])
    if a==0 and b==0:
       break
    for i in range (a):
        print('#'*b)
    print()
words = input()
ans = 'No’

for word in words:
  if words.count(word) %2 != 0:
    breake
  else:
    ans = ('Yes’)
    
print(ans)

### FIXED CODE ###

words = input()
ans = 'No'
for word in words:
  if words.count(word) %2 != 0:
    break
else:
  ans ='Yes'  
print(ans)
import sys
 
 
def gcd(a, b):
    return gcd(b, a % b) if a % b else b
 
 
def lcm(a, b):
    return a * b / gcd(a, b)
 
for line in sys.stdin:
    data = map(int, line.split())
    a, b, c, d, e, f = data
    ix = lcm(a, d) / a
    jx = lcm(a, d) / d
    iy = lcm(b, e) / b
    jy = lcm(b, e) / e
    x = (c*1.0*iy - f*jy) / (a*iy - d*jy)
    y = (c*1.0*ix - f*jx) / (b*ix - e*jx)
    print "%.3f %.3f" % (round(x, 4), round(y, 4))

### FIXED CODE ###

import sys


def gcd(a, b):
    return gcd(b, a % b) if a % b else b


def lcm(a, b):
    return a * b / gcd(a, b)

for line in sys.stdin:
    data = map(int, line.split())
    a, b, c, d, e, f = data
    if a == 0:
        y = c * 1.0 / b
        x = (f - e * y) * 1.0 / d
        print "%.3f %.3f" % (round(x, 4), round(y, 4))
        continue
    if b == 0:
        x = c * 1.0 / a
        y = (f - d * x) * 1.0 / e
        print "%.3f %.3f" % (round(x, 4), round(y, 4))
        continue
    if d == 0:
        y = f * 1.0 / e
        x = (c - b * y) * 1.0 / a
        print "%.3f %.3f" % (round(x, 4), round(y, 4))
        continue
    if e == 0:
        x = f * 1.0 / d
        y = (c - a * x) * 1.0 / b
        print "%.3f %.3f" % (round(x, 4), round(y, 4))
        continue

    ix = lcm(a, d) / a
    jx = lcm(a, d) / d
    iy = lcm(b, e) / b
    jy = lcm(b, e) / e
    x = (c*1.0*iy - f*jy) / (a*iy - d*jy)
    y = (c*1.0*ix - f*jx) / (b*ix - e*jx)
    print "%.3f %.3f" % (round(x, 4), round(y, 4))
if input() == ABC:
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

print("ABC" if input() == "ARC" else "ARC")
n, k = [int(i) for i in input().split()]
return n - k + 1

### FIXED CODE ###

n, k = [int(i) for i in input().split()]
print(n - k + 1)
a,b,c=int(input())
print(max(a,b,c)-min(a,b,c))

### FIXED CODE ###

a,b,c=map(int,input().split())
print(max(a,b,c)-min(a,b,c))
l =input().split()
a=0
b=0
for i in range(0,2):
  if len(i) = 5:
    a = a+1
  if len(i) = 7:
    b = b+1
if a=2 and b=1:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a = list(map(int,input().split()))
b = 0
c = 0
for i in a:
  if i == 7:
    b += 1
  elif i == 5:
    c += 1
 
if b == 1 and c == 2:
  print("YES")
else:
  print("NO")
import collections
n,k=list(map(int,input().split()))
l_n=[(v+1)%k for v in range(n)]
c = collections.Counter(l_n)
m = len(c)
ret=0
if k%2==0:
    for i in range(0,m,k/2):
        for j in range(0,m,k/2):
            if (i+j)%k==0:
                for r in range(0,r,k/2):
                    if(i+r)%k==0 and(r+j)%k==0:
                        ret+=c[i]*c[j]*c[r]
else:
    for i in range(0,m,k):
        for j in range(0,m,k):
            if (i+j)%k==0:
                for r in range(0,m,k):
                    if (i+r)%k ==0 and (r+j)%k==0:
                        ret+=c[i]*c[j]*c[r]
print(ret)
            
    


### FIXED CODE ###

n, k = map(int, input().split())
print(sum([1 if v % k == 0 else 0 for v in range(1, n+1)])**3 +
      sum([1 if v % k == k/2 else 0 for v in range(1, n+1)])**3)
a,b=map(int, input().split())
s = [list(map(int, input().split())) for i in range(b)]
s = sum(s, [])
L = [-1]*[0]*(a-1)
ans = 0
ab = 10**(a-1)

for i in range(b):
    if L[s[i*2]-1] == 0:
        L[s[i*2]-1] = s[i*2+1]
    if L[s[i*2]-1] != 0 and L[s[i*2]-1] == s[i*2+1]:
        pass
    if L[s[i*2]-1] != 0 and L[s[i*2]-1] != s[i*2+1]:
        ans += 1

if ans == 0:
    if a == 1 and b == 0:
        print(0)
    if a != 1 and b == 0:
        print(ab)
    if b !=0 and L[0] == 0:
        print('-1')
    if b !=0 and L[0] == -1:
        T = ''.join(map(str,L[1:a]))
        ab = ab + int(T)
        print(ab)
    if b !=0 and L[0] != -1:
        T = ''.join(map(str,L))
        print(T)
if ans != 0:
    print('-1')

### FIXED CODE ###

import sys
 
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for f in range(m)]
if n == 1:
    start = 0
    end = 10
else:
    start = 10**(n-1)
    end = 10**n
for i in range(start, end):
  x = False
  for j in sc:
    if str(i)[j[0]-1] != str(j[1]):
      x = True
      break
  if x:
    continue
  print(i)
  sys.exit()
print(-1)
n,k=map(int,input().split())
l=list(map(int,input().split()))
f=[l.count(i) for i in range(0,n)]
f.sort()
print(sum(f[0:n-k]))

### FIXED CODE ###

print(input().count("1"))
def is_lunlun(i):
    list_i = list(str(i))
    for j in range(len(list_i)-1):
        if int(list_i[j]) == 0:
            if int(list_i[j+1]) not in [1,9,0]:
                return False
        elif int(list_i[j]) == 1:
            if int(list_i[j+1]) not in [0,1,2]:
                return False
        elif int(list_i[j]) == 9:
            if int(list_i[j+1]) not in [8,9]:
                return False
        else:
            if abs(int(list_i[j]) - int(list_i[j+1])) > 1:
                return False
    return True



if __name__ == '__main__':
    k = int(input())
    lunlun = (i for i in range(3234566667) if is_lunlun(i))
    for count, i in enumerate(lunlun):
        if count == k:
            print(i)
            break

        

### FIXED CODE ###

if __name__ == '__main__':
    a,b,c = input().split(" ")
    a,b = b,a
    a,c = c,a
    print(a, b, c)
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 16 23:09:00 2018

@author: sakas
"""
A,B = map(int(input()))

if A>9 or B>9:
    print(":(")
else:
    print("Yay!")


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jun 16 23:09:00 2018

@author: sakas
"""
A, B = map(int, input().split())
if A>=9 or B>=9:
    print(":(")
else:
    print("Yay!")
A=list(map(int(input.split())))
if A[0]+A[1]+A[2]>=22:
  print("bust")
else:
  print("win")

### FIXED CODE ###

A=list(map(int,input().split()))
if A[0]+A[1]+A[2]>=22:
  print("bust")
else:
  print("win")
import math

input()
ip = input().split()
data = []
for i in ip:
    data.append(int(i))


def lcmbase(x, y):
    return x * y / math.gcd(int(x), int(y))

def lcm(num):
    buf = num[0]
    for i in range(1, len(num)):
        buf = lcmbase(num[i], buf)
    return buf

usedata = int(lcm(data) - 1)

suming = 0
for i in data:
    suming += usedata % i

print(suming)

### FIXED CODE ###

input()
ip = input().split()
data = []
ans = 0
for i in ip:
    ans += int(i) - 1

print(ans)
import math
def baisu(x,a):
    if x%a ==0:
        return int(x//a)
    else:
        x -=1
        return baisu(x,a)

a,b,c,d = map(int,input().split())

to_a = a - baisu(a,c) - baisu(a,d) + baisu(a,c*d/math.gcd(c,d))
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,c*d/math.gcd(c,d))

if a%c == 0 or a%d == 0:
    print(int(to_b - to_a))
else:
    print(int(to_b-to_a+1))

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def baisu(x,a):
    return int(x//a)
a,b,c,d = map(int,input().split())

to_a = a-1 - baisu(a-1,c) - baisu(a-1,d) + baisu(a-1,c*d//gcd(c,d))
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,c*d//gcd(c,d))

print(to_b - to_a)
a, b= [int(input()) for _ in range(2)]
import math
c=a*(10**len(str(b)))+b
if int(math.sqrt(c)) == math.sqrt(c):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from math import sqrt
a, b = input().split()
n = int(a+b)
if(int(sqrt(n))**2 == n):
    print("Yes")
else:
    print("No")
N = int(input())
H = map(int, input().split())
H.append(1000000001)

max = H[0]
for i in range(N):
    if max >= H[i+1] + 2:
        print('No')
        break
    if max < H[i+1]:
        max = H[i+1]
        
else:
    print('Yes')
        

### FIXED CODE ###

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

max = H[0]
for i in range(N):
    if max >= H[i+1] + 2:
        print('No')
        break
    if max < H[i+1]:
        max = H[i+1]
        
else:
    print('Yes')
# import sys
# sys.setrecursionlimit(2000)

N = int(input())
COR = [tuple((map(int, input().split()))) for _ in range(N)]


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        if self.n <= 2:
            return 0
        return len(self.x) * len(self.y) - self.n
        
def grouping(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            grouping(group, x_, xcor, ycor)
    
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

### FIXED CODE ###

# import sys
# sys.setrecursionlimit(20000)


N = int(input())
COR = [tuple((map(int, input().split()))) for _ in range(N)]


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = 0
        self.y = 0
        self.xy = {}
        
    def new_cor_n(self):
        return self.x * self.y - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x += 1
    for y in xcor[x][0]:
        if (x, y) not in group.xy:
            group.n += 1
            group.xy[(x, y)] = None
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y += 1
        for x_ in ycor[y][0]:
            if (x_, y) not in group.xy:
                group.n += 1
                group.xy[(x_, y)] = None
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)
from math import gcd 
N, X = list(map(int, input().split()))
x = list(map(int, input().split()))
ans = gcd(abs(x[0] - X), abs(x[1] - X))
for i in range(2, N):
  ans = gcd(ans, abs(x[i] - X)
print(ans)

### FIXED CODE ###

from math import gcd 
N, X = list(map(int, input().split()))
x = list(map(int, input().split()))
if(N == 1): print(abs(x[0] - X))
else:
  ans = gcd(abs(x[0] - X), abs(x[1] - X))
  for i in range(2, N):
  	ans = gcd(ans, abs(x[i] - X))
    
  print(ans)
if __name__ == "__main__":
    date = input().split(" ")
    if date[0] <= date[1]:
        print(date[0])
    else:
        print(date[0]-1)

### FIXED CODE ###

if __name__ == "__main__":

    date = input().replace("　", " ").split(" ")

    if date[0] <= date[1]:
        print(date[0])
    else:
        print(int(date[0])-1)
target = int(input())
curAns = target

for i in range(1,target**0.5):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

### FIXED CODE ###

n=int(input())
ans=n
for i in range(int(n**0.5),0,-1):
    if n%i==0:
        ans=n//i+i-2
        break
print(ans)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    MAX = max(A)
    LCM = {num: 0 for num in range(2, MAX+1)}
    A2Factor = [{num: 0 for num in range(2, MAX+1)} for _ in range(N)]

    def factorization(n, idx):
        temp = n
        flag = 0
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                flag = 1
                LCM[i] = max(LCM[i], cnt)
                A2Factor[idx][i] = cnt
        if temp!=1:
            LCM[temp] = max(LCM[temp], 1)
            A2Factor[idx][temp] = 1 
        if not flag:
            LCM[n] = max(LCM[n], 1)
            A2Factor[idx][n] = 1
        return LCM, A2Factor

    for idx in range(N):
        LCM, A2Factor = factorization(A[idx], idx)

    ans = 0
    for i in range(N):
        ans_dict = {}
        tmp = 1
        for num in range(2, MAX+1):
            ans_dict[num] = abs(LCM[num] - A2Factor[i][num])
        for key, value in ans_dict.items():
            tmp *= pow(key, value, p)
            tmp %= p
        ans += tmp%p
    print(ans % p)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
A = list(map(int, input().split()))
M = max(S)
r = sum(M - a for a in A)
print((r + 3 * (r % 2)) // 2)

### FIXED CODE ###

S = list(map(int, input().split()))
M = max(S)
r = sum(M - i for i in S)
print((r + 3 * (r % 2)) // 2)
from collections import Counter 
n=int(input())
a=sorted(list(map(int,input().split())))
b=[]
c=[]
for i in list(Counter(a).values()):
  b.append(i)
for i in list(Counter(a).keys()):
  c.append(i)
ans=c.pop()*((b[-1])-1)
m=a[-1]
f=len(b)
for _ in range(f-2,-1,-1):
  i=-2
  if b[-1]>b[i]:
    b[-1]-=b[i]
    b.pop(i)
    c.pop(i)    
    ans+=b[i]*m
  else:
    ans+=m*b[-1]
    b[i]-=b[-1]
    m=c.pop()
    ans+=m*b[i]
    b.pop()
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))[::-1]
ans=0
for i in range(1,n):
  ans+=a[i//2]
print(ans)
n = int(input())
d = len(str(n))
c = 0
for i in range(1, d):
  if i % 2 == 1:
  	c += 9 * (10**(i-1))
  
c += n - int('9'*(d-1)) if d % 2 == 1 else 0

print(c)

### FIXED CODE ###

n = int(input())
d = len(str(n))
a = [9, 0, 900, 0, 9000]
c = 0
for i in range(1, d):
  if i % 2 == 1:
  	c += 9 * (10**(i-1))
  
if d == 1:
  c += n
else:
  c += n - int('9'*(d-1)) if d % 2 == 1 else 0

print(c)
def main(A,D,N):
    K=min(N,len(D))
    for i in range(K):
        if A[i]>D[i]:
            return sum(D[:i]+A[i:])
    return sum(D[:K]+A[K:])

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
CB=[]
for m in range(M):
    b,c=map(int,input().split())
    CB.append([c,b])
CB.sort()
CB.reverse()
D=[]
while len(D)<N and CB!=[]:
    D.append(CB[0][0])
    CB[0][1]-=1
    if CB[0][1]==0:
        CB.remove(CB[0])
for cb in CB:
    B+=[cb[0]]*cb[1]
print(main(A,D,N))

### FIXED CODE ###

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

BC=[]
for m in range(M):
    b,c=map(int,input().split())
    BC.append([b,c])

A.sort()
BC.sort(key=lambda x:x[1],reverse=True)

D=[]
for [b,c] in BC:
    D+=[c]*b
    if len(D)>N:
        break

if len(D)<N:
    D+=[0]*(N-len(D))

AD=[max(A[i],D[i]) for i in range(N)]
 
print(sum(AD))