number-b

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 numberb.in 输出文件 numberb.out

【题目描述】


有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。


【来源】

在此键入。