F. Fishermen
flows; graph matchings; greedy
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.