7275: BZOJ3275:Number

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1


输入格式

第一行一个正整数n,表示数的个数。 第二行n个正整数a1,a2,?an    


输出格式

最大的和。  


样例输入

5
3  4 5 6 7
 
 
 

样例输出

22
 
 

提示

n<=3000。


题目来源

网络流

加入题单

上一题 下一题 算法标签: