题目描述

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

输入格式

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

输出格式

最大的和。

5
3  4 5 6 7

22
 
 

提示

n<=3000。

题目来源

网络流