1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<cmath>  5 #include<queue>  6 #include<cstring>  7 using namespace std;  8 const int INF=1e8;  9 const int mxn=9000; 10 int read(){ 11     int x=0,f=1;char ch=getchar(); 12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14     return x*f; 15 } 16 struct edge{ 17     int from,v,nxt; 18     int f,w; 19 }e[mxn<<1]; 20 int hd[mxn],mct=1;// 21 void add_edge(int u,int v,int c,int w){ 22     e[++mct].v=v;e[mct].from=u;e[mct].nxt=hd[u];e[mct].f=c;e[mct].w=w;hd[u]=mct;return; 23 } 24 // 25 int n,m; 26 int S,T; 27 int ans=0; 28 int win[mxn],lose[mxn],c[mxn],d[mxn]; 29 // 30 int dis[mxn]; 31 bool inq[mxn]; 32 int pre[mxn<<1]; 33 void SPFA(int s){ 34     memset(dis,0x3f,sizeof dis); 35     memset(pre,-1,sizeof pre); 36     queue<int>q; 37     dis[s]=0; 38     inq[s]=1; 39     q.push(s); 40     while(!q.empty()){ 41         int u=q.front();q.pop();inq[u]=0; 42         for(int i=hd[u];i;i=e[i].nxt){ 43             if(!e[i].f)continue; 44             int v=e[i].v; 45             if(dis[v]>dis[u]+e[i].w){ 46                 dis[v]=dis[u]+e[i].w; 47                 pre[v]=i;//记录前驱边  48                 if(!inq[v]){ 49                     inq[v]=1; 50                     q.push(v); 51                 } 52             } 53         } 54     } 55     return; 56 } 57 void maxflow(int s,int t){ 58     SPFA(s); 59     while(pre[t]!=-1){ 60         int tmp=INF; 61         for(int i=pre[t];i!=-1;i=pre[e[i].from]) 62             tmp=min(tmp,e[i].f); 63         ans+=dis[t]*tmp; 64         for(int i=pre[t];i!=-1;i=pre[e[i].from]){ 65             e[i].f-=tmp; 66             e[i^1].f+=tmp; 67         } 68         SPFA(s); 69     } 70     return; 71 } 72 int a[mxn],b[mxn]; 73 int main() 74 { 75     int i,j,u,v; 76     n=read();m=read(); 77     for(i=1;i<=n;i++){ 78         win[i]=read();lose[i]=read(); 79         c[i]=read();d[i]=read(); 80     } 81     for(i=1;i<=m;i++){ 82         a[i]=read();b[i]=read(); 83         ++lose[a[i]];++lose[b[i]]; 84     } 85     for(i=1;i<=n;i++){//假设全部都输掉  86         ans+=c[i]*win[i]*win[i]; 87         ans+=d[i]*lose[i]*lose[i]; 88     } 89     S=0;T=m+n+2; 90     for(i=1;i<=m;i++){ 91         add_edge(S,i,1,0); 92         add_edge(i,S,0,0); 93         add_edge(i,m+a[i],1,0); 94         add_edge(m+a[i],i,0,0); 95         add_edge(i,m+b[i],1,0); 96         add_edge(m+b[i],i,0,0); 97         //a 98         int cost=c[a[i]]*(2*win[a[i]]+1)-d[a[i]]*(2*lose[a[i]]-1); 99         add_edge(m+a[i],T,1,cost);100         add_edge(T,m+a[i],0,-cost);101         win[a[i]]++;lose[a[i]]--;102         //b103         cost=c[b[i]]*(2*win[b[i]]+1)-d[b[i]]*(2*lose[b[i]]-1);104         add_edge(m+b[i],T,1,cost);105         add_edge(T,m+b[i],0,-cost);106         win[b[i]]++;lose[b[i]]--;107     }108     maxflow(S,T);109     printf("%d\n",ans);110     return 0;111 }