Description：

$n$ 支球队，设 $x_i$ 和 $y_i$ 分别是这支球队在本赛季中的胜负场次，那么这赛季的支出是 $C_i\times x_i^2+D_i\times y_i^2$ ，已知第 $i$ 支球队已经赢了 $a_i$ 场输了 $b_i$ 场，给出后面 $m$ 场比赛的双方，求最小总支出。

$2\leqslant n\leqslant 5000,0\leqslant m\leqslant 1000$

Solution：

首先可能会有一些错误的想法，比如说把一场比赛当作一个流，然后用那种拆边的方式处理平方的贡献，然后把赢和输分别计算拆成两个点那样，但是会发现如果要拆边的话就必须明确每个流的来源，写一下就会发现区分不出来，于是考虑别的方法。

平方不太好做，我们可以利用差分来去掉平方，也就是先假设之后所有比赛两支队伍都是输，那么每一场比赛会给一个人贡献赢一次的收益，考虑这样的贡献： $$ C_i\times (a_i+1)^2+D_i\times (b_i-1)^2-C_i\times a_i^2-D_i\times b_i^2=2a_iC_i+C_i-2b_iD_i+D_i $$ 不难发现这个费用是随着 $a_i$ 变大 $b_i$ 变小单调递增的，于是我们就可以拆边费用流了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 5010

int A[MAXN],B[MAXN],C[MAXN],D[MAXN];

int cnt[MAXN];

#define MAXM 1010

struct game

{

	int u,v;

}g[MAXM];

// EK begin

#define MAXP (MAXN + MAXM)

#define MAXE (MAXM * 5)

int s,t;

struct edge

{

    int to,nxt,f,v;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP];

inline void add(int a,int b,int c,int d)

{

    e[edgenum] = (edge){b,lin[a],c,d};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0,-d};lin[b] = edgenum++;

    return;

}

int d[MAXP],rate[MAXP],pre[MAXP];

bool v[MAXP];

#define INF 0x3f3f3f3f

inline bool SPFA()

{

    memset(d,0x3f,sizeof(d));d[s] = 0;

    queue<int> q;q.push(s);

    rate[s] = INF;

    while(!q.empty())

    {

        register int k = q.front();q.pop();

        v[k] = false;

        for(register int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(d[e[i].to] > d[k] + e[i].v && e[i].f)

            {

                d[e[i].to] = d[k] + e[i].v;

                rate[e[i].to] = min(rate[k],e[i].f);

                pre[e[i].to] = i;

                if(!v[e[i].to])

                {

                    v[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    return d[t] < INF;

}

inline int flow()

{

    for(register int i = t;i != s;i = e[pre[i] ^ 1].to)

    {

        e[pre[i]].f -= rate[t];

        e[pre[i] ^ 1].f += rate[t];

    }

    return rate[t] * d[t];

}

inline int EK()

{

    register int ans = 0;

    while(SPFA())ans += flow();

    return ans; 

}

// EK end

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);

	int ans = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&g[i].u,&g[i].v);

		++B[g[i].u];++B[g[i].v];

		++cnt[g[i].u];++cnt[g[i].v];

	}

	for(int i = 1;i <= n;++i)ans += A[i] * A[i] * C[i] + B[i] * B[i] * D[i];

	s = n + m + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1,cura = A[i],curb = B[i];j <= cnt[i];++j,++cura,--curb)

		{

			add(i,t,1,2 * cura * C[i] - 2 * curb * D[i] + C[i] + D[i]);

		}

	}

	for(int i = 1;i <= m;++i)

	{

		add(s,i + n,1,0);

		add(i + n,g[i].u,1,0);

		add(i + n,g[i].v,1,0);

	}

	cout << ans + EK() << endl;

	return 0;

}