[Solution] Fishermen Codeforces Solution

F. Fishermen

time limit per test

6 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

There are 𝑛$n$ fishermen who have just returned from a fishing trip. The 𝑖$i$-th fisherman has caught a fish of size 𝑎𝑖$a_i$.

The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size 𝑛$n$). However, they are not entirely honest, and they may "increase" the size of the fish they have caught.

Formally, suppose the chosen order of the fishermen is [𝑝1,𝑝2,𝑝3,…,𝑝𝑛]$[p_1,p_2,p_3,\dots ,p_n]$. Let 𝑏𝑖$b_i$ be the value which the 𝑖$i$-th fisherman in the order will tell to the other fishermen. The values 𝑏𝑖$b_i$ are chosen as follows:

• the first fisherman in the order just honestly tells the actual size of the fish he has caught, so 𝑏1=𝑎𝑝1$b_1=a_{p_1}$;
• every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for 𝑖>1$i>1$, 𝑏𝑖$b_i$ is the smallest integer that is both strictly greater than 𝑏𝑖−1$b_{i-1}$ and divisible by 𝑎𝑝𝑖$a_{p_i}$.

For example, let 𝑛=7$n=7$, 𝑎=[1,8,2,3,2,2,3]$a=[1,8,2,3,2,2,3]$. If the chosen order is 𝑝=[1,6,7,5,3,2,4]$p=[1,6,7,5,3,2,4]$, then:

• 𝑏1=𝑎𝑝1=1$b_1=a_{p_1}=1$;
• 𝑏2$b_2$ is the smallest integer divisible by 2$2$ and greater than 1$1$, which is 2$2$;
• 𝑏3$b_3$ is the smallest integer divisible by 3$3$ and greater than 2$2$, which is 3$3$;
• 𝑏4$b_4$ is the smallest integer divisible by 2$2$ and greater than 3$3$, which is 4$4$;
• 𝑏5$b_5$ is the smallest integer divisible by 2$2$ and greater than 4$4$, which is 6$6$;
• 𝑏6$b_6$ is the smallest integer divisible by 8$8$ and greater than 6$6$, which is 8$8$;
• 𝑏7$b_7$ is the smallest integer divisible by 3$3$ and greater than 8$8$, which is 9$9$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

You have to choose the order of fishermen in a way that yields the minimum possible ∑𝑖=1𝑛𝑏𝑖$\sum _{i=1}^n{b}_i$.

Input

The first line contains one integer 𝑛$n$ (1≤𝑛≤1000$1\le n\le 1000$) — the number of fishermen.

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤106$1\le a_i\le {10}^6$).

Output

Print one integer — the minimum possible value of ∑𝑖=1𝑛𝑏𝑖$\sum _{i=1}^n{b}_i$ you can obtain by choosing the order of fishermen optimally.