One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $n$ machines, and the power of the $i$-th machine is $a_i$. 

This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $x$, then choose one machine and reduce the power of its machine by $x$ times, and at the same time increase the power of one another machine by $x$ times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $i$ and $j$, and one integer $x$ such that $x$ is a divisor of $a_i$, and change powers as following: $a_i = \frac{a_i}{x}$, $a_j = a_j \cdot x$

Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 5 \cdot 10^4$) — the number of machines.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) — the powers of the machines.


-----Output-----

Print one integer — minimum total power.


-----Examples-----
Input
5
1 2 3 4 5

Output
14

Input
4
4 2 4 4

Output
14

Input
5
2 4 2 3 7

Output
18



-----Note-----

In the first example, the farmer can reduce the power of the $4$-th machine by $2$ times, and increase the power of the $1$-st machine by $2$ times, then the powers will be: $[2, 2, 3, 2, 5]$.

In the second example, the farmer can reduce the power of the $3$-rd machine by $2$ times, and increase the power of the $2$-nd machine by $2$ times. At the same time, the farmer can leave is be as it is and the total power won't change.

In the third example, it is optimal to leave it be as it is.

Difficulty: interview

Starter code:

Solutions:
import copy
import fractions
import itertools
import numbers
import string
import sys

###

def to_basex(num, x):
	while num > 0:
		yield num % x
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d*p
		p *= x
	return ret

###

def core():
	n = int(input())
	a = [int(x) for x in input().split()]
	
	m = min(a)
	s = sum(a)
	ans = s
	for ai in a:
		for d in range(1, ai+1):
			if ai % d == 0:
				cand = s - ai - m + ai//d + m*d
				ans = min(ans, cand)
	
	print(ans)


core()




















n = int(input())
a = list(map(int,input().split()))
a = sorted(a)

base_sum = sum(a)

smallest = a[0]
min_sum = sum(a)
if n==1:
    print(min_sum)
    return

seen = set()
for x in a[1:]:
    if x in seen:continue
    seen.add(x)
    without = base_sum - a[0] - x
    for div in range(2,x+1):
        if x%div == 0:
            min_sum = min(min_sum,without + smallest*div + x//div)

print (min_sum)

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))






n=nn()

l=lm()

l.sort()

s=sum(l)

ms=s
for num in l:
	for j in range(1,num//2+1):
		if num%j==0:
			newnum=num//j
			newsum=s-num+newnum-l[0]+j*l[0]

			ms=min(newsum,ms)


print(ms) 


def fac(n):
    b=[1]
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            b.append(i)
            if i!=n//i:
                b.append(n//i)
    return b
    
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
m=10**9
a.sort()
for i in a[::-1]:
    for j in fac(i):
        m=min(m,s+ a[0]*j  + i//j - a[0] - i)
        #print(m,i,j)
print(m)        

n = int(input())
arr = list(map(int, input().split()))
d = dict()
for el in arr:
    d[el] = d.get(el, 0) + 1
min_ans = 0
for el1 in d:
    for el2 in d:
        if el1 != el2:
            for x in range(2, 101):
                if el1 % x == 0:
                    min_ans = min(min_ans, el1 // x + el2 * x - el1 - el2)
print(sum(arr) + min_ans)


n = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
p = sum(arr)
a = []
d = {}
for i in range(1, 101):
    d[i] = 0
for i in arr:
    d[i] += 1
for i in range(1, 101):
    for j in range(1, 101):
        if j % i == 0:
            for k in range(1, 101):
                a.append((j, k, (k + j - j // i - k * i)))
m = -100000000
for i in a:
    if i[0] == i[1]:
        if d[i[0]] >= 2:
            m = max(m, i[2])
    else:
        if d[i[0]] != 0 and d[i[1]] != 0:
            m = max(m, i[2])
print(p - m)

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
if n == 1:
    print(s)
    return
ans = s
c = {}
for i in range(n):
    if a[i] not in c:
        c[a[i]] = 0
    c[a[i]] += 1

ds = {}
for i in range(1, 102):
    ds[i] = []
    for j in range(1, i+1):
        if i % j == 0:
            ds[i].append(j)

for v1 in c.keys():
    for v2 in c.keys():
        if v1 == v2 and c[v1] == 1:
            continue
        for d in ds[v1]:
            ch = -(v1 - v1//d) + (v2*d - v2)
            ans = min(ans, s + ch)

print(ans)

def read_nums():
    return [int(x) for x in input().split()]


def get_divisors(num):
    res = []
    for i in range(2, num + 1):
        if num % i == 0:
            res.append(i)
    return res


def solve(powers):
    s = sum(powers)
    smallest = min(powers)
    cur_res = s
    for num in set(powers):
        for divisor in get_divisors(num):
            candidate = s - num + num // divisor - smallest + smallest * divisor
            cur_res = min(cur_res, candidate)
    print(cur_res)


def main():
    n, = read_nums()
    powers = read_nums()
    solve(powers)


def __starting_point():
    main()

__starting_point()

list_int_input = lambda inp: list(map(int, inp.split()))
int_input = lambda inp: int(inp)
string_to_list_input = lambda inp: list(inp)


n=int(input())
lst=list(map(int,input().split()))
minn=min(lst)
summ=sum(lst)
sum1=summ
val=-1
for i in range(50,1,-1):
    for j in lst:
        if j%i==0:
            val=i
            sum1=min(summ-minn-j+int(j/i)+(i*minn),sum1)
print(sum1)



import sys
from math import *
from fractions import gcd
readints=lambda:list(map(int, input().strip('\n').split()))

n = int(input())
a = list(readints())

s = sum(a)
m = min(a)

best = s
for x in a:
    for d in range(1,x+1):
        if x%d==0:
            dx=x/d
            dm=m*d
            s2 = s-x-m+dx+dm
            best = min(best,s2)

best=int(best)

print(best)
    



n = int(input())
arr = list(map(int,input().strip().split()))

x = sum(arr)
arr = sorted(arr)
ans = [x]
for i in range(n-1,-1,-1):
    for j in range(1,arr[i]+1):
        if arr[i]%j==0:
            if arr[i]+arr[0] > (arr[i]//j)+arr[0]*j:
                ans.append(x-arr[i]-arr[0]+arr[0]*j+(arr[i]//j))

print(min(ans))


import math

def __starting_point():
    n = int(input())
    a = input().split()
    for i in range(n):
        a[i] = int(a[i])
    
    b = sum(a)
    a = list(set(a))
    n = len(a)
    improv = 0
    for i in range(n):
        for j in range(n):
            if a[i] < a[j]:
                found = False
                k = 2
                current = 0
                while not found:
                    if a[j]%k == 0:
                        found = True
                        current = max(a[i]+a[j]-a[i]*k-a[j]//k, current)
                    if found and k < math.sqrt(a[j]/a[i]):
                        found = False
                    k = k+1
                improv = max(improv, current)
    print(b - improv)
__starting_point()

import math

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
ans = s
for i in range(n - 1, 0, -1):
    cur = s - a[0] - a[i]
    for j in range(2, int(math.sqrt(a[i]) + 1)):
        if a[i] % j == 0:
            ans = min(ans, cur + a[0] * j + a[i] // j)
print(ans)


n = int(input())
l = list(map(int,input().split()))
cnt = sum(l)
ans = []
ans.append(cnt)
l = set(l)
l = list(l)
for i in range(len(l)):
    tmp = []
    for k in range(1,l[i] + 1):
        if l[i] % k == 0:
            tmp.append(k)
    for k in range(len(tmp)):
        for j in range(len(l)):
            if i == j:
                continue
            ans.append(cnt - l[i] - l[j] + l[i] // tmp[k] + l[j] * tmp[k])
ans.sort()
print(ans[0])


def factors(a):
        f=[]
        for i in range(2,a):
                if a%i==0:f.append(i)
        return f
n=int(input())
a=list(map(int,input().split()))
a.sort()
sm=sum(a)
ans=sm
i=n-1
while i>0:
        f=factors(a[i])
        if f:
                for j in f:
                        x,y=a[i]//j,a[0]*j
                        ans=min(ans,sm-a[i]-a[0]+x+y)
        i-=1
print(ans)

n = int(input())
a = list(map(int,input().split()))
su = sum(a)
a.sort()
mi = a[0]
i = 0
ma = 0
s = list(set(a))
n = len(s)
while i < n:
	j=2
	while j<s[i]:
		if s[i]%j == 0:
			ans = (j-1)*(int(s[i]/j)-mi)
			ma = max(ma,ans)		
		j+=1
	i+=1	
print(su-ma)


n = int(input())
a = [int(t) for t in input().split(' ')]

min_number = min(a)

defaultpower = sum(a)
minpower = defaultpower

for m in range(2, max(a)+1):
    maxi = -1
    for i in range(n):
        if a[i] % m == 0 and (maxi == -1 or a[i] > a[maxi]):
            maxi = i

    if maxi == -1: continue

    power = defaultpower - min_number - a[maxi] + min_number * m + a[maxi] // m

    minpower = min(power, minpower)

print(minpower)


from collections import deque, Counter, OrderedDict
from heapq import nsmallest, nlargest
from math import ceil,floor,log,log2,sqrt,gcd,factorial
def binNumber(n,size=1):
    return bin(n)[2:].zfill(size)

def iar():
    return list(map(int,input().split()))

def ini():
    return int(input())

def isp():
    return list(map(int,input().split()))

def sti():
    return str(input())

def par(a):
    return ' '.join(list(map(str,a)))

class pair:
    def __init__(self,f,s):
        self.fi = f
        self.se = s
    def __lt__(self,other):
        return (self.fi,self.se) < (other.fi,other.se)

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def __starting_point():
    n = ini()
    a = iar()
    mi = min(a)
    mis = sum(a)
    mas = mis
    for i in a:
        if i == mi:
            continue
        j = 2
        while j*j <= i:
            if i%j == 0:
                c1 = i//j
                c2 = mi*j
                x = mas - mi - i + c1 + c2
                if x < mis:
                    mis = x
                if j != i//j:
                    k = i//j
                    c1 = i//k
                    c2 = mi*k
                    x = mas + c1 + c2 - mi - i
                    if x < mis:
                        mis = x
            j += 1
    print(mis)

__starting_point()

input()
L=list(map(int,input().split()))
L.sort()
a=L[0]
k=0
for i in L:
    for j in range(1,int(i**0.5+1)):
        if i%j==0 and (a+i)-(i//j+a*j)>k:k=(a+i)-(i//j+a*j)
print(sum(L)-k)

# Bismillahirahmanirahim
# Soru 1
#
# nv = list(map(int, input().split()))
#
# n = nv[0] - 1
# v = nv[1]
# if v >= n:
#     print(n)
#     quit()
# k = 2
# money = v
# while n - v > 0:
#     n = n - 1
#     money += k
#     k += 1
# print(money)

#Soru2
def carpan(n):
    lst = []
    sq = n**0.5 + 1
    for i in range(2,int(sq)+1):
        if n%i == 0:
            lst.append(i)
    return lst


n = int(input())
lst = list(map(int, input().split()))
lst = sorted(lst, reverse=True)
mn = lst[-1]
total = sum(lst)
large = 0
for i in lst:
    mx = i
    lst1 = carpan(mx)
    for j in lst1:
        if mx + mn - (mx/j + mn*j) > large:
            large = mx + mn - (mx/j + mn*j)
print(int(total-large))





def inpl(): return list(map(int, input().split()))

N = int(input())
A = inpl()
A.sort()
ma = A[0]
ans = 0
for b in A[1:]:
    for x in range(1, b//2 + 1):
        if b%x:
            continue
        ans = max(ans, (ma + b)-ma*x-b//x)
print(sum(A)-ans)


n = int(input())
A = list(map(int, input().split()))
M = min(A)
ahaha = 0
fl = 0
su = 0
for q in A:
    su += q
    if q != M:
        for d in range(2, int(q**0.5) + 1):
            if q % d == 0:
                ahaha = max(ahaha, -(-M-q+M*d+q//d))
                ahaha = max(ahaha, -(-M - q + M * (q // d) + q // (q // d)))
print(su - ahaha)

n = int(input())
a = [int(item) for item in input().split()]

a.sort()


s = sum(a)
ans = s

for i in range(len(a)):
    for x in range(2, int(a[i] ** .5) + 1):
        if a[i] % x == 0:
            ans = min(ans, s - a[0] - a[i] + a[0] * x + a[i] // x)

print(ans)


def get():
    return list(map(int,input().split()))
def pf(n): 
    a=[]
    i=1
    while i*i<n:
        if n%i==0:
            a+=[i]
            a+=[n//i]
        i+=1
    if i*i==n:
        a+=[i]
    return a
n=int(input())
b=get()
c=list(set(b))
a=101*[0]
for i in range(1,101):
    a[i]=pf(i)
s=sum(b)
c.sort()
m=c[0]
ans=0
for i in c:
    for j in a[i]:
        ans=max(ans,(j-1)*(i//j-m))
print(s-ans)