Problem F: 【GESP5】晚宴

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：6 Solved：4

Description

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

Input

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

Output

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

Sample Input Copy 

5
3 5 7 35 105

Sample Output Copy 

38

HINT

1≤ n ≤ 1000;    1 ≤ vi≤ 1000000 。

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