题目描述

CC 联盟是一个拥有极高人气的球队联盟。CC 联盟里现有 $n$ 支 $A$ 球队，在 $08-09$ 赛季球队之间要进行一些比赛。现在赛季已经过去一半，第 $i$ 支球队目前已经赢了 $win_i$ 场，输了 $lose_i$ 场。

现在赛季还剩下 $m$ 场比赛，赛程已确定，第 $i$ 场比赛的对阵双方为第 $a_i$ 支球队和 $b_i$ 支球队。比赛不会出现平局，也就是说每一场比赛都一定有一个胜者和一个败者。在 CC 联盟，一个球队所能活的的收益与他们在这个赛季中的胜负场次相关，当然赢得越多，球队能够获得的收益就越大。若第 $i$ 支球队在本赛季赢了 $x$ 场，输了 $y$ 场，那么第 $i$ 支球队在本赛季获得的总收益为 $c_ix^2+d_iy^2$，其中 $d_i\leq c_i$。

身为另一个 DD 联盟的主席兼 boss 的邪恶的小阳阳当然不希望 CC 联盟本赛季获得的总收益太大，所以她想知道本赛季全部结束后 CC 联盟获得的总收益最少为多少，其中联盟的总收益等于每个球队本赛季获得收益之和。注意一个赛季中每个球队总的比赛场次可能不一样，两个队伍之间可能打多场比赛。

输入格式

第一行两个正整数 $n,m$ 分别表示 CC 联盟里球队的个数以及本赛季剩余的比赛场次。

接下来 $n$ 行，每行四个非负整数 $win_i,lose_i,c_i,d_i$ 分别表示第 $i$ 支球队本赛季目前的胜负场次以及球队获得收益的相关系数。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示剩余的第 $i$ 场比赛的对阵双方为第 $a_i$ 支球队和第 $b_i$ 支球队，数据保证 $a_i\not = b_i,1\leq a_i,b_i\leq n$。

输出格式

一个整数表示联盟里所有球队收益之和的最小值。

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

43

数据规模与约定

对于 $20\%$ 的数据，$2\leq n\leq 10$，$0\leq m\leq 20$。

对于 $100\%$ 的数据，$0\leq d_i\leq c_i\leq 10$，$0\leq win_i,lose_i\leq 50$，$2\leq n\leq 5\times 10^3$，$0\leq m\leq 10^3$。