1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-07-29 15:51:58
4
 * @Last Modified by: WildRage
5
 * @Last Modified time: 2017-07-29 16:05:11
6
 */
7
#include <cstdio>
8
#include <queue>
9
#include <cstring>
10
using namespace std;
11
int win[5005], lose[5005];
12
int C[5005], D[5005], du[5005];
13
const int INF = 0x3f3f3f3f;
14
class Mincost
15
{
16
  public:
17
    int first[20005], p;
18
    Mincost()
19
    {
20
        memset(first, -1, sizeof(first));
21
    }
22
    class edge
23
    {
24
      public:
25
        int END, S, next, cap, cost;
26
    } v[100005];
27

28
    void add(int a, int b, int f, int c)
29
    {
30
        v[p].END = b, v[p].next = first[a], v[p].S = a, v[p].cap = f, v[p].cost = c, first[a] = p++;
31
        v[p].END = a, v[p].next = first[b], v[p].S = b, v[p].cap = 0, v[p].cost = -c, first[b] = p++;
32
    }
33
    int dis[20005], pre[20005];
34
    bool vis[20005];
35
    bool spfa(int S, int E)
36
    {
37
        memset(dis, 0x3f, sizeof(dis));
38
        memset(pre, -1, sizeof(pre));
39
        memset(vis, 0, sizeof(vis));
40
        queue<int> Q;
41
        Q.push(S);
42
        vis[S] = 1;
43
        dis[S] = 0;
44
        while (!Q.empty())
45
        {
46
            int u = Q.front();
47
            Q.pop();
48
            vis[u] = 0;
49
            for (int i = first[u]; i != -1; i = v[i].next)
50
            {
51
                if (!v[i].cap)
52
                    continue;
53
                if (dis[v[i].END] > dis[u] + v[i].cost)
54
                {
55
                    dis[v[i].END] = dis[u] + v[i].cost;
56
                    pre[v[i].END] = i;
57
                    if (!vis[v[i].END])
58
                    {
59
                        vis[v[i].END] = 1;
60
                        Q.push(v[i].END);
61
                    }
62
                }
63
            }
64
        }
65
        return dis[E] != 0x3f3f3f3f;
66
    }
67
    int MinCost(int S, int T)
68
    {
69
        int ans = 0, flow;
70
        while (spfa(S, T))
71
        {
72
            flow = INF;
73
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
74
                flow = min(flow, v[i].cap);
75
            for (int i = pre[T]; i != -1; i = pre[v[i].S])
76
                v[i].cap -= flow, v[i ^ 1].cap += flow;
77
            ans += dis[T] * flow;
78
        }
79
        return ans;
80
    }
81
} Min;
82
int main(int argc, char const *argv[])
83
{
84
    int n, m, a, b;
85
    int S = 0, T = 10005;
86
    scanf("%d%d", &n, &m);
87
    for (int i = 1; i <= n; i++)
88
    {
89
        scanf("%d%d%d%d", &win[i], &lose[i], &C[i], &D[i]);
90
    }
91
    int ans = 0;
92
    for (int i = 1; i <= m; i++)
93
    {
94
        Min.add(S, i, 1, 0);
95
        scanf("%d%d", &a, &b);
96
        Min.add(i, m + a, 1, 0);
97
        Min.add(i, m + b, 1, 0);
98
        du[a]++, du[b]++;
99
    }
100
    for (int i = 1; i <= n; i++)
101
        lose[i] += du[i];
102
    for (int i = 1; i <= n; i++)
103
        ans += lose[i] * lose[i] * D[i] + win[i] * win[i] * C[i];
104
    for (int i = 1; i <= n; i++)
105
    {
106
        for (int j = 1; j <= du[i]; j++)
107
        {
108
            Min.add(m + i, T, 1, 2 * win[i] * C[i] + C[i] + D[i] - 2 * lose[i] * D[i]);
109
            lose[i]--;
110
            win[i]++;
111
        }
112
    }
113
    printf("%d\n", ans + Min.MinCost(S, T));
114
    //while (1)
115
        ;
116
    return 0;
117
}