#P2895. 球队预算

    ID: 2002 传统题 1000ms 512MiB 尝试: 154 已通过: 114 难度: 7 上传者: 标签>CF2200提高+/省选-差分转化指定流量最小费用流势能优化费用流Dijkstra

球队预算

题目描述

在一个篮球联赛里,有 nn 支球队,球队的支出是和他们的胜负场次有关系的,具体来说,第 ii 支球队的赛季总支出是 ci×x2+di×y2c_i\times x^2+d_i\times y^2,di≤cid_i\leq c_i。

其中 x,yx,y 分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半,每只球队分别取得了 aia_i 场胜利和 bib_i 场失利。而接下来还有 mm 场比赛要进行。问联盟球队的最小总支出是多少。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行每行四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i。

再接下来 mm 行每行两个整数 s,ts,t 表示第 ss 支队伍和第 tt 支队伍之间将有一场比赛,注意两只队间可能有多场比赛。

输出格式

一行一个整数表示总支出的最小值。

3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
43

数据规模与约定

对于 20%20\% 的数据,2≤n≤102\leq n\leq 10,0≤m≤200\leq m\leq 20;

对于 100%100\% 的数据,2≤n≤5×1032\leq n\leq 5\times 10^3,0≤m≤1030\leq m\leq 10^3,0≤di≤ci≤100\leq d_i\leq c_i\leq 10,0≤ai,bi≤500\leq a_i,b_i\leq 50。