## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 $\left[{p}_{1},{p}_{2},{p}_{3},\dots ,{p}_{n}\right]$. 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 ${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 $i>1$${b}_{i}$ is the smallest integer that is both strictly greater than ${b}_{i-1}$ and divisible by ${a}_{{p}_{i}}$.

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

• ${b}_{1}={a}_{{p}_{1}}=1$;
• ${b}_{2}$ is the smallest integer divisible by $2$ and greater than $1$, which is $2$;
• ${b}_{3}$ is the smallest integer divisible by $3$ and greater than $2$, which is $3$;
• ${b}_{4}$ is the smallest integer divisible by $2$ and greater than $3$, which is $4$;
• ${b}_{5}$ is the smallest integer divisible by $2$ and greater than $4$, which is $6$;
• ${b}_{6}$ is the smallest integer divisible by $8$ and greater than $6$, which is $8$;
• ${b}_{7}$ is the smallest integer divisible by $3$ and greater than $8$, which is $9$.

Solution Click Below:-  👉
👇👇👇👇👇

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

Input

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

The second line contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{6}$).

Output

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