#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<string>#include<stack>#include<queue>#include<vector>#include<map>#include<set>#include<iostream>#define pb push_backusing namespace std;typedef unsigned long long ULL;typedef long long LL;const int MAXN = 505;const int MAXM = 50005;const int INF = 0x3f3f3f3f;struct Edge{ int to,next,cap,flow,cost;} edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int have[MAXN], want[MAXN];int N;void init(int n){ N = n; tol = 0; memset(head, -1, sizeof(head));}void addedge(int u,int v,int cap,int cost){ edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++;}bool spfa(int s,int t){ queue<int>q; for(int i = 0; i < N; i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1)return false; else return true;}int minCostMaxflow(int s,int t,int &cost){ int flow = 0; cost = 0; while(spfa(s,t)) { int Min = INF; for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow;}void solve(){ int n, m; while(~scanf("%d %d", &n, &m)){ init(2*n+2); int sum = 0, haveSum = 0; for(int i=1; i<=n; i++){ scanf("%d %dn", &have[i], &want[i]); sum += have[i]; haveSum += want[i]; addedge(0, i, have[i], 0); addedge(i, i+n, INF, 0); addedge(i+n, 2*n+1, want[i], 0); } for(int i=0; i<m; i++){ int u, v; scanf("%d %d", &u, &v); addedge(u, v+n, INF, 1); addedge(v, u+n, INF, 1); addedge(u+n, v, INF, 1); addedge(v+n, u, INF, 1); } if(haveSum != sum){ puts("-1"); continue; } int ans = 0; int k = minCostMaxflow(0, 2*n+1, ans); if(k == sum) printf("%dn", ans); else puts("-1"); }}int main(void){ solve(); return 0;}
