#G1178. [GESP202606 五级] 晚宴

[GESP202606 五级] 晚宴

[GESP202606 五级] 晚宴

时间限制:1.0 s 内存限制:512.0 MB

题目描述

小明去参加晚宴。晚宴中有 nn 个菜肴,每个菜肴都有一个美味度,第 ii 个菜肴的美味度为 viv_i。

晚宴规定小明只能恰好选取两道菜肴,并且这两道菜肴的美味度必须要互质(即最大公约数为 1)。

请帮助小明选取两道菜肴,使得两道菜肴美味度之和最大。

输入格式

输入 2 行。

第一行为一个正整数 nn,表示菜肴的个数;

第二行为 nn 个整数 v1,v2,…,vnv_1, v_2, \dots, v_n,表示菜肴的美味度,整数之间以空格分隔。

输出格式

输出一个整数,表示两道互质菜肴美味度之和的最大值。

样例 #1

样例输入 #1

5
3 5 7 35 105

样例输出 #1

38

样例解释

最优选择是 3 和 35。

注意到,105 与其他任意菜肴的最大公约数都大于 1,因此无法参与合法选择。

数据范围

  • 2≤n≤10002 \le n \le 1000,1≤vi≤10000001 \le v_i \le 1000000。
  • 数据保证不存在相同美味度的菜肴。
  • 数据保证至少存在一种选取两道菜肴的方案。