number-b

【题目描述】

有n个正整数，现在需要从中选出一些数，使得这些数的和最大。若两个数a和b同时满足以下条件，则a和b不能同时被选：

（1）存在正整数c，使得a^2+b^2=c^2。

（2）(a,b)=1，即a和b的最大公约数为1。

【输入格式】

第一行一个正整数n，表示数的个数。

第二行n个正整数a1,a2,…,an。

【输出格式】

最大的和。

【样例输入】

5
3 4 5 6 7

【样例输出】

22

【提示】

100%的数据中，n<=3000。

所有数小于等于100000。

【来源】

在此键入。