1 /**************************************************************  2     Problem: 3275  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1560 ms  7     Memory:6760 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <cstring> 13 #include <algorithm> 14   15 using namespace std; 16 const int N = 6005; 17 const int M = 500001; 18 const int inf = (int) 1e9; 19     20 struct edges{ 21     int next, to, f; 22     edges() {} 23     edges(int _next, int _to, int _f) : next(_next), to(_to), f(_f) {} 24 } e[M]; 25   26 int n, m, ans, S, T; 27 int first[N], tot = 1; 28 int q[N], a[N >> 1], d[N]; 29   30 inline int read() { 31     int x = 0; 32     char ch = getchar(); 33     while (ch < ‘0‘ || ‘9‘ < ch) 34         ch = getchar(); 35     while (‘0‘ <= ch && ch <= ‘9‘) { 36         x = x * 10 + ch - ‘0‘; 37         ch = getchar(); 38     } 39     return x; 40 } 41   42 inline void add_edge(int x, int y, int z){ 43     e[++tot] = edges(first[x], y, z); 44     first[x] = tot; 45 } 46     47 inline void Add_Edges(int x, int y, int z){ 48     add_edge(x, y, z); 49     add_edge(y, x, 0); 50 } 51     52 bool bfs(){ 53     memset(d, 0, sizeof(d)); 54     q[1] = S, d[S] = 1; 55     int l = 0, r = 1, x, y; 56     while (l < r){ 57         ++l; 58         for (x = first[q[l]]; x; x = e[x].next){ 59             y = e[x].to; 60             if (!d[y] && e[x].f) 61                 q[++r] = y, d[y] = d[q[l]] + 1; 62         } 63     } 64     return d[T]; 65 } 66     67 int dinic(int p, int limit){ 68     if (p == T || !limit) return limit; 69     int x, y, tmp, rest = limit; 70     for (x = first[p]; x; x = e[x].next){ 71         y = e[x].to; 72         if (d[y] == d[p] + 1 && e[x].f && rest){ 73             tmp = dinic(y, min(rest, e[x].f)); 74             rest -= tmp; 75             e[x].f -= tmp, e[x ^ 1].f += tmp; 76             if (!rest) return limit; 77         } 78     } 79     if (limit == rest) d[p] = 0; 80     return limit - rest; 81 } 82     83 int Dinic(){ 84     int res = 0, x; 85     while (bfs()) 86         res += dinic(S, inf); 87     return res; 88 } 89   90 int gcd(int a, int b) { 91     return b ? gcd(b, a % b) : a; 92 } 93   94 inline int Sqr(int x) { 95     return x * x; 96 } 97   98 inline bool check(int x, int y) { 99     int t = x * x + y * y;100     return Sqr(((int) sqrt(t))) == t && gcd(x, y) == 1;101 }102  103 int main() {104     int i, j;105     n = read();106     S = n << 1 | 1, T = S + 1;107     for (i = 1; i <= n; ++i) {108         a[i] = read();109         Add_Edges(S, i, a[i]);110         Add_Edges(i + n, T, a[i]);111         ans += a[i];112     }113     for (i = 1; i <= n; ++i)114         for (j = i + 1; j <= n; ++j)115             if (check(a[i], a[j]))116                 Add_Edges(i, j + n, inf), Add_Edges(j, i + n, inf);117     printf("%d\n", ans - Dinic() / 2);118     return 0;119 }