codeforces#P1728F. Fishermen

Fishermen

Description

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 $[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 $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 = [1, 8, 2, 3, 2, 2, 3]$. If the chosen order is $p = [1, 6, 7, 5, 3, 2, 4]$, 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$.

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

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$).

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

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\limits_{i=1}^{n} b_i$ you can obtain by choosing the order of fishermen optimally.

7
1 8 2 3 2 2 3
10
5 6 5 6 5 6 5 6 5 6
33
165