C0599 晚宴

试题名称：晚宴

时间限制：1.0s

内存限制：512.0MB

题目描述

小明去参加晚宴。晚宴中有 n 个菜肴，每个菜肴都有一个美味度，第 i 个菜肴的美味度为 vi。晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为1）。请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。

输入格式

输入2行，

第一行为一个正整数 n，表示菜肴的个数；

第二行为 n 个整数 v1, v2, ..., vn，表示菜肴的美味度，整数之间以空格分隔。

输出格式

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

样例

输入样例1

5
3 5 7 35 105

输出样例1

38

样例解释1

最优选择是3和35。

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

数据范围

2 ≤ n ≤ 1000，1 ≤ vi ≤ 1000000

数据保证不存在相同美味度的菜肴。

数据保证至少存在一种选取两道菜肴的方案。