number-b

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file numberb.in Output file 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。


【来源】

在此键入。