ADAFEAR - Ada and Primal Fear

no tags 

As you might already know, Ada the Ladybug is a farmer. She grows many vegetables. During past months, her crop was attacked by colony of parasites. Each vegetable was attacked by Ai parasites. Ada has only limited answer for this. She bought a few bottles with Primal Fear, which is a mixture agains parasites.

Primal Fear works in following way: Each Primal Fear bottle has a power assigned to it (which is coincidentally a prime number). If it is applied to a vegetable with N parasites on it, either the N is divisible by its power, then the size of colony is reduced to N/power, or - if the size is not divisible - then it has no effect. Also, as soon as you apply mixture against a colony, the rest of colony will become immune agains Primal Fear.

Ada didn't know what to buy so she bought one bottle of every possible power. Can you find out the best strategy to fight agains parasites?

Input

The first line of input will contain 1 ≤ N ≤ 1000, the number of vegetable.

 

The line will contain N numbers 1 ≤ Ai ≤ 2000, the size of colony on ith vegetable.

Output

Print the minimum sum of sizes of colonies which could be achieved after applying Primal Fear optimally.

Example Input

3
2 8 6

Example Output

8

Example Input

4
6 6 6 6

Example Output

17

Example Input

3 
7 4 22

Example Output

5

Example Input

3
11 22 17

Example Output

13

Example Input

2
77 11

Example Output

12

hide comments
vaibhav2303: 2018-07-14 14:02:33

Last edit: 2018-07-15 15:56:59
wisfaq: 2017-12-28 12:32:27

Last edit: 2017-12-28 13:57:22
morass: 2017-12-28 00:04:35

@Prateek Agarwal: Good day to you. Nope, since as you kill part of colony by Primal Fear, the rest of colony will become immune agains Primal Fear. Wish you a nice day ~ Good Luck!

Prateek Agarwal: 2017-12-27 11:03:02

Can more than one Primal Fears be applied on a single colony?


Added by:Morass
Date:2017-12-26
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All