С рыбалки вернулось \(n\) рыбаков. \(i\)-й рыбак поймал рыбу размера \(a_i\).
Рыбаки выберут какой-то порядок, в котором они будут рассказывать, какого размера они поймали рыбу (порядок — это просто перестановка размера \(n\)). Рыбаки не совсем честны, и во время рассказа могут «увеличить» размер пойманной рыбы.
Формально, пусть рыбаки рассказывают про пойманную ими рыбу в порядке \([p_1, p_2, p_3, \dots, p_n]\). Пусть \(b_i\) — размер рыбы, названный \(i\)-м рыбаком в выбранном порядке. Значения \(b_i\) считаются следующим образом:
- первый рыбак в выбранном порядке просто честно называет размер пойманной рыбы, то есть \(b_1 = a_{p_1}\);
- каждый следующий рыбак хочет назвать минимальное значение, которое будет строго больше значения, названного предыдущим рыбаком, а также делится на размер пойманной этим рыбаком рыбы. То есть для \(i > 1\) значение \(b_i\) равно минимальному целому числу, которое одновременно строго больше \(b_{i-1}\) и делится на \(a_{p_i}\).
Например, пусть \(n = 7\), \(a = [1, 8, 2, 3, 2, 2, 3]\). Если выбранный порядок рыбаков \(p = [1, 6, 7, 5, 3, 2, 4]\), тогда:
- \(b_1 = a_{p_1} = 1\);
- \(b_2\) — минимальное целое число, которое делится на \(2\) и превосходит \(1\), то есть \(2\);
- \(b_3\) — минимальное целое число, которое делится на \(3\) и превосходит \(2\), то есть \(3\);
- \(b_4\) — минимальное целое число, которое делится на \(2\) и превосходит \(3\), то есть \(4\);
- \(b_5\) — минимальное целое число, которое делится на \(2\) и превосходит \(4\), то есть \(6\);
- \(b_6\) — минимальное целое число, которое делится на \(8\) и превосходит \(6\), то есть \(8\);
- \(b_7\) — минимальное целое число, которое делится на \(3\) и превосходит \(8\), то есть \(9\).
Вы хотите выбрать такой порядок, в котором рыбаки будут называть размер пойманной рыбы, чтобы минимизировать значение \(\sum\limits_{i=1}^{n} b_i\).