4043: [GESP202606 五级] 晚宴
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
小明去参加晚宴。晚宴中有 个菜肴，每个菜肴都有一个美味度，第 个菜肴的美味度为 。
晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 ）。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
输入
输入 行，
第一行为一个正整数 ，表示菜肴的个数；
第二行为 个整数 表示菜肴的美味度，整数之间以空格分隔。
输出
输出一个整数，表示两道互质菜肴美味度之和的最大值。
样例输入 复制
5
3 5 7 35 105样例输出 复制
38提示
样例解释 1
最优选择是 和 。
注意到， 与其他任意菜肴的最大公约数都大于 ，因此无法参与合法选择。
数据范围
, 。
数据保证不存在相同美味度的菜肴。
数据保证至少存在一种选取两道菜肴的方案。