1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+514 #define maxm 100000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)23 #define mod 100000000724 using namespace std;25 inline int read()26 {27     int x=0,f=1;char ch=getchar();28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30     return x*f;31 }32 int n,m,k,mincost,tot=1,s,t,a[maxn],b[maxn],c[maxn],d[maxn],ss[maxn],head[maxn],from[2*maxm];33 bool v[maxn];34 queue<int>q;35 struct edge{int from,go,next,v,c;}e[2*maxm];36 void ins(int x,int y,int z,int w)37 {38     e[++tot]=(edge){x,y,head[x],z,w};head[x]=tot;39 }40 void insert(int x,int y,int z,int w)41 {42     ins(x,y,z,w);ins(y,x,0,-w);43 }44 bool spfa()45 {46     for (int i=s;i<=t;i++){v[i]=0;d[i]=inf;}47     q.push(s);d[s]=0;v[s]=1;48     while(!q.empty())49     {50         int x=q.front();q.pop();v[x]=0;51         for (int i=head[x],y;i;i=e[i].next)52          if(e[i].v&&d[x]+e[i].c<d[y=e[i].go])53          {54             d[y]=d[x]+e[i].c;from[y]=i;55             if(!v[y]){v[y]=1;q.push(y);}56          }57     }58     return d[t]!=inf;59 }60 void mcf()61 {62     while(spfa())63     {64         int tmp=inf;65         for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v);66         mincost+=d[t]*tmp;67         for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}68     }69 }70 int main()71 {72     freopen("input.txt","r",stdin);73     freopen("output.txt","w",stdout);74     n=read();m=read();s=0;t=n+m+1;75     for1(i,n)a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();76     for1(i,m)77     {78         int x=read(),y=read();ss[x]++;ss[y]++;79         insert(s,i+n,1,0);80         insert(i+n,x,1,0);81         insert(i+n,y,1,0);82     }83     for1(i,n)b[i]+=ss[i];84     for1(i,n)85     {86        int x=a[i],y=b[i];87        for1(j,ss[i])88         {89          insert(i,t,1,2*c[i]*x-2*d[i]*y+c[i]+d[i]);90          x++;y--;91         }92     }93     int ans=0;94     for1(i,n)ans+=c[i]*a[i]*a[i]+d[i]*b[i]*b[i];95     mcf();96     printf("%d\n",ans+mincost);97     return 0;98 }