Description:


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

  1. 存在正整数C,使a*a+b*b=c*c
  2. gcd(a,b)=1

Input:


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

Output:


最大的和。

Sample Input:


Sample Output:


HINT:


n<=3000。

题解:


观察一下发现两个奇数不会满足第一个条件,两个偶数不会满足第二个条件。

所以我们奇数放一边偶数放一边。

然后如果两个数不能同时选连一条流量为INF的边。
源点向奇数连奇数大小的边,偶数向汇点连偶数大小的边。

然后总和减去最小割就可以了。