1 /**************************************************************
2 Problem: 3275
3 User: idy002
4 Language: C++
5 Result: Accepted
6 Time:3616 ms
7 Memory:1176 kb
8 ****************************************************************/
9
10 #include
11 #include
12 #include
13 #include
14 #define min(a,b) ((a)<(b)?(a):(b))
15 #define oo 0x3f3f3f3f
16 #define N 6010
17 using namespace std;
18
19 typedef long long dnt;
20 struct Edge {
21 int u, v, f;
22 Edge( int u, int v, int f ):u(u),v(v),f(f){}
23 };
24 struct Dinic {
25 int src, dst;
26 vector edge;
27 vector<int> g[N];
28 int dep[N], cur[N], qu[N], bg, ed;
29 void init( int src, int dst ) {
30 this->src = src;
31 this->dst = dst;
32 }
33 void adde( int u, int v, int f ) {
34 g[u].push_back( edge.size() );
35 edge.push_back( Edge(u,v,f) );
36 g[v].push_back( edge.size() );
37 edge.push_back( Edge(v,u,0) );
38 }
39 bool bfs() {
40 memset( dep, 0, sizeof(dep) );
41 qu[bg=ed=1] = src;
42 dep[src] = 1;
43 while( bg<=ed ) {
44 int u=qu[bg++];
45 for( int t=0; t ) {
46 Edge &e = edge[g[u][t]];
47 if( e.f && !dep[e.v] ) {
48 dep[e.v] = dep[e.u] + 1;
49 qu[++ed] = e.v;
50 }
51 }
52 }
53 return dep[dst];
54 }
55 int dfs( int u, int a ) {
56 if( u==dst || a==0 ) return a;
57 int remain=a, past=0, na;
58 for( int &t=cur[u]; t ) {
59 Edge &e=edge[g[u][t]];
60 Edge &ve=edge[g[u][t]^1];
61 if( e.f && dep[e.v]==dep[e.u]+1 && (na=dfs(e.v,min(remain,e.f))) ) {
62 remain -= na;
63 past += na;
64 e.f -= na;
65 ve.f += na;
66 if( !remain ) break;
67 }
68 }
69 return past;
70 }
71 int maxflow() {
72 int rt=0;
73 while( bfs() ) {
74 memset( cur, 0, sizeof(cur) );
75 rt += dfs(src,oo);
76 }
77 return rt;
78 }
79 }D;
80
81 int n;
82 int src, dst;
83 int aa[N], sum;
84 int gcd( int a, int b ) {
85 return b ? gcd(b,a%b) : a;
86 }
87 bool ok( int a, int b ) {
88 if( gcd(a,b)!=1 ) return false;
89 dnt cc = (dnt)a*a + (dnt)b*b;
90 dnt c = (dnt)sqrt(cc);
91 if( c*c!=cc && (c+1)*(c+1)!=cc ) return false;
92 return true;
93 }
94 int main() {
95 scanf( "%d", &n );
96 src = n+1, dst = n+2;
97 D.init( src, dst );
98 for( int i=1; i<=n; i++ ) {
99 scanf( "%d", aa+i );
100 sum += aa[i];
101 if( aa[i]&1 )
102 D.adde( src, i, aa[i] );
103 else
104 D.adde( i, dst, aa[i] );
105 }
106 for( int i=1; i<=n; i++ ) {
107 if( !(aa[i]&1) ) continue;
108 for( int j=1; j<=n; j++ ) {
109 if( aa[j]&1 ) continue;
110 if( !ok(aa[i],aa[j]) ) continue;
111 D.adde( i, j, oo );
112 }
113 }
114 printf( "%d\n", sum-D.maxflow() );
115 }