Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Sasha and Magnetic Machines

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 02:13:23 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|