← 返回题目列表

Codeforces · 731/F

F. 显卡

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

小弗拉德喜欢流行的电脑游戏Bota-2。最近,开发人员宣布了名为 Bota-3 的新附加组件。当然,弗拉德立即购买,却发现他的电脑对于新游戏来说太旧了,需要更新。

商店中有n张显卡,第i张显卡的功率等于整数值ai。由于弗拉德希望确保新游戏能够正常运行,因此他想购买的不是一张,而是几张显卡,并使用尖端技术将它们的力量结​​合起来。为了使用该技术,选择其中一张卡作为主导卡,并将其他视频卡附加到它作为辅助卡。为了使这项新技术发挥作用,要求每个辅助视频卡的功率都能被主视频卡的功率整除。为了实现任何辅助显卡的功率可以降低到小于或等于当前功率的任何整数值。但主显卡的功率应保持不变,即不能降低。

Vlad 拥有无限的金钱,因此他可以购买任何一套显卡。帮助他确定应该购买哪些显卡,以便在选择领先的显卡并可能减少其他显卡的一些功率以使它们协同工作后,他将获得最大的视频功率总价值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 商店中显卡的数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 200 000) — 显卡的功率。

输出

输出的唯一一行应包含一个整数值 - 一起工作的显卡的最大可能总功率。

示例

输入 #1

4
3 2 15 9

输出 #1

27

输入 #2

4
8 2 2 7

输出 #2

18

注意

在第一个示例中,最好购买功率为 3、15 和 9 的显卡。应选择功率为 3 的显卡作为主导显卡,所有其他显卡都将与其兼容。这样,总功率就是 3 + 15 + 9 = 27。如果他买了所有显卡,并选择功率为 2 的显卡作为主导,则所有其他显卡的功率都应该减 1,这样总功率就是 2 + 2 + 14 + 8 = 26,即小于 27。请注意,不允许降低主导显卡的功率,即无法获得主显卡的功率。总功率 3 + 1 + 15 + 9 = 28。

在第二个示例中,最佳答案是购买所有显卡并选择以 2 为主导的显卡。功率为 7 的显卡需要将功率降低到 6。总功率将为 8 + 2 + 2 + 6 = 18。