1 /**************************************************************  2     Problem: 2400  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:552 ms  7     Memory:3180 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 typedef long long ll; 16 const int N = 505; 17 const int M = 2005; 18 const int Me = 200005; 19 const int inf = 1e9; 20   21 struct edge { 22     int x, y; 23     edge() {} 24     edge(int _x, int _y) : x(_x), y(_y) {} 25 } E[M]; 26   27 struct edges { 28     int next, to, f; 29     edges() {} 30     edges(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {} 31 } e[Me]; 32   33 int n, m, S, T; 34 int a[N], del[N]; 35 int tot, first[N]; 36 int d[N], q[N]; 37 ll ans; 38   39 inline int read() { 40     int x = 0, sgn = 1; 41     char ch = getchar(); 42     while (ch < ‘0‘ || ‘9‘ < ch) { 43         if (ch == ‘-‘) sgn = -1; 44         ch = getchar(); 45     } 46     while (‘0‘ <= ch && ch <= ‘9‘) { 47         x = x * 10 + ch - ‘0‘; 48         ch = getchar(); 49     } 50     return sgn * x; 51 } 52   53 inline void Add_Edges(int x, int y, int f) { 54     e[++tot] = edges(first[x], y, f), first[x] = tot; 55     e[++tot] = edges(first[y], x, 0), first[y] = tot; 56 } 57   58 bool bfs() { 59     int l, r, x, y; 60     memset(d, 0, sizeof(d)); 61     d[q[1] = S] = 1; 62     for (l = r = 1; l != (r + 1) % N; (++l) %= N)  63         for (x = first[q[l]]; x; x = e[x].next) 64             if (!d[y = e[x].to] && e[x].f) 65                 d[q[(++r) %= N] = y] = d[q[l]] + 1; 66     return d[T]; 67 } 68   69 int dfs(int p, int lim) { 70     if (p == T || !lim) return lim; 71     int x, y, tmp, rest = lim; 72     for (x = first[p]; x; x = e[x].next)  73         if (d[y = e[x].to] == d[p] + 1 && (tmp = min(e[x].f, rest) > 0)) { 74             rest -= (tmp = dfs(y, tmp)); 75             e[x].f -= tmp, e[x ^ 1].f += tmp; 76             if (!rest) return lim; 77         } 78     if (lim == rest) d[p] = 0; 79     return lim - rest; 80 } 81   82 int Dinic() { 83     int res = 0; 84     while (bfs()) 85         res += dfs(S, inf); 86     return res; 87 } 88   89 void build_graph(int t) { 90     int i; 91     tot = 1, memset(first, 0, sizeof(first)); 92     for (i = 1; i <= n; ++i) 93         if (a[i] >= 0) 94             if (a[i] & t) Add_Edges(i, T, inf); 95             else Add_Edges(S, i ,inf); 96     for (i = 1; i <= m; ++i) 97         Add_Edges(E[i].x, E[i].y, 1), Add_Edges(E[i].y, E[i].x, 1); 98 } 99  100 void find(int p) {101     int x, y;102     d[p] = 1;103     for (x = first[p]; x; x = e[x].next)104         if (e[x ^ 1].f && !d[y = e[x].to]) find(y);105 }106  107 void calc_val(int t) {108     int i;109     memset(d, 0, sizeof(d));110     find(T);111     for (i = 1; i <= n; ++i)112         if (d[i]) del[i] += t;113 }114  115 ll calc_ans() {116     ll res = 0;117     int i;118     for (i = 1; i <= n; ++i)119         res += a[i] >= 0 ? a[i] : del[i];120     return res;121 }122  123 int main() {124     int i;125     n = read(), m = read();126     S = n + 1, T = n + 2;127     for (i = 1; i <= n; ++i)128         a[i] = read();129     for (i = 1; i <= m; ++i)130         E[i] = edge(read(), read());131     for (i = 0; i <= 30; ++i) {132         build_graph(1 << i);133         ans += (ll) (1 << i) * Dinic();134         calc_val(1 << i);135     }136     printf("%lld\n%lld\n", ans, calc_ans());137     return 0;138 }