题目描述

在一个篮球联赛里，有 $n$ 支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第 $i$ 支球队的赛季总支出是 $c_i\times x^2+d_i\times y^2$，$d_i\leq c_i$。

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

输入格式

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

接下来 $n$ 行每行四个整数 $a_i,b_i,c_i,d_i$。

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

输出格式

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

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\%$ 的数据，$2\leq n\leq 5\times 10^3$，$0\leq m\leq 10^3$，$0\leq d_i\leq c_i\leq 10$，$0\leq a_i,b_i\leq 50$。