← 返回题目列表

Codeforces · 1113/B

B. 萨莎和磁力机

中文机器翻译题面 查看原题

有一天,萨沙参观了农民 2D 和他著名的磁力农场。在这个农场里,农作物在特殊磁场的影响下生长。磁场的维持由$$$n$$$台机器提供,第$$$i$$$台机器的功率为$$$a_i$$$。

今年2D决定培养一种新的文化,但具体是什么他没有说。为了新文化的成功成长,有必要稍微改变机器的力量。 2D 最多可以选择一个任意整数 $$$x$$$ 一次,然后选择一台机器并将其机器的功率降低 $$$x$$$ 倍,同时将另一台机器的功率提高 $$$x$$$ 倍(所有机器的功率必须保持正整数)。请注意,如果他愿意,他可能不会这样做。更正式地说,2D 可以选择两个这样的索引 $$$i$$$ 和 $$$j$$$,以及一个整数 $$$x$$$,使得 $$$x$$$ 是 $$$a_i$$$ 的除数,并按如下方式更改幂: $$$a_i = \frac{a_i}{x}$$$, $$$a_j = a_j \cdot x$$$

萨沙很好奇,所以他想计算一下农民能达到的最小总功率。机器太多了,萨沙无法应付计算,帮助他吧!

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — 机器数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 机器的能力。

输出

打印一个整数——最小总功率。

示例

输入 #1

5
1 2 3 4 5

输出 #1

14

输入 #2

4
4 2 4 4

输出 #2

14

输入 #3

5
2 4 2 3 7

输出 #3

18

注意

在第一个例子中,农民可以将第 $$$4$$$-th 机器的功率减少 $$$2$$$ 倍,并将 $$$1$$$-st 机器的功率增加 $$$2$$$ 倍,则功率将为:$$$[2, 2, 3, 2, 5]$$$。

在第二个示例中,农民可以将 $$$3$$$-rd 机器的功率减少 $$$2$$$ 倍,并将 $$$2$$$-nd 机器的功率增加 $$$2$$$ 倍。同时,农民可以保持原样,总功率不会改变。

在第三个示例中,最好保持原样。