Ta dựng đồ thị có ~n^2 + n~ node như sau:

• Có ~n^2~ node có dạng ~x_{i, j}~ (~1 \le i, j \le n~); nếu chọn node ~x_{i, j}~ thì sẽ thu về lợi nhuận là ~a_i \cdot b_j~.

• Có ~n~ node có dạng ~y_i~ (~1 \le i \le n~); nếu chọn node ~y_i~ thì phải chi ~c_i~.

Ta dựng các điều kiện sau trên đồ thị:

• Với mỗi node ~x_{i, j}~, muốn chọn node này phải chọn node ~y_i~ và ~y_j~.

• Với mỗi tiêu chí ~(u, v)~ từ để bài, muốn chọn node ~y_u~ phải chọn node ~y_v~.

Bài toán đưa về bài toán closure (project selection), đọc thêm ở đây. Dựng luồng sẽ mất độ phức tạp ~O(n^2 + m)~.

///This code may not be accurate
///aureg109 orz
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define ii pair<int,int>
#define sz(x) (int) (x).size()
#define pb push_back
using namespace std;
template<class T1,class T2> bool maximize(T1 &a,T2 b) {return(a<b ? a=b,1:0);};
template<class T1,class T2> bool minimize(T1 &a,T2 b) {return(a>b ? a=b,1:0);};
const int N=210;
ll a[N],b[N],c[N],a2[N],b2[N],c2[N];
bool adj[N][N];
bool vis[N];
int low[N],num[N],cnt,nnode;
int newnode[N];
int n,m;
stack<int> s;
bool haveedge[N][N];
void dfs(int u)
{
    vis[u]=1;
    low[u]=num[u]=++cnt;
    s.push(u);
    for (int v=1;v<=n;v++) if (adj[u][v])
    {
        if (!vis[v]) dfs(v);
        low[u]=min(low[u],low[v]);
    }
    if (1)
    {
        ++nnode;
        int v;
        while (1)
        {

            int v=s.top();
            newnode[v]=nnode;
            low[u]=num[u]=1e9;
            s.pop();
            if (u==v) break;
        } 

    }
}
struct FlowEdge
{
    int u,v;
    long long cap,flow=0;
    FlowEdge(int u,int v,long long cap) : u(u), v(v), cap(cap) {}
};
struct Dinic
{
    int n,m=0;
    vector <FlowEdge> edges;
    vector <vector <int>> g;
    vector <int> level,ptr;
    queue<int> q;
    int s,t;
    Dinic(int n,int s,int t) : n(n),s(s),t(t)
    {
        g.resize(n+5);
        level.resize(n+5);
        ptr.resize(n+5);
    }
    void add_edge(int u,int v,long long w)
    {
        edges.push_back({u,v,w});
        edges.push_back({v,u,0});
        g[u].push_back(m);
        g[v].push_back(m+1);
        m+=2;
    }
    bool bfs()
    {
        while (q.size())
        {
            int u=q.front();
            q.pop();
            for (int id:g[u])
            {
                if (edges[id].cap-edges[id].flow==0) continue;
                if (level[edges[id].v]!=-1) continue;
                level[edges[id].v]=level[u]+1;
                q.push(edges[id].v);
            }
        }
        return (level[t]!=-1);
    }
    long long dfs(int u,long long pushed=1e18)
    {
        if (pushed==0) return 0;
        if (u==t) return pushed;
        for (int& cid=ptr[u]; cid<(int) (g[u]).size(); cid++)
        {
            int id=g[u][cid];
            int v=edges[id].v;
            if (level[u]+1!=level[v]||edges[id].cap-edges[id].flow==0) continue;
            int tr=dfs(v,min(pushed,edges[id].cap-edges[id].flow));
            if (!tr) continue;
            edges[id].flow+=tr;
            edges[id^1].flow-=tr;
            return tr;
        }
        return 0;
    }
    long long flow()
    {
        long long maxflow=0ll;
        while ( true)
        {
            fill(level.begin(),level.end(),-1);
            fill(ptr.begin(),ptr.end(),0);
            level[s]=0;
            q.push(s);
            if (!bfs()) break;
            while (long long pushed=dfs(s)) maxflow+=pushed;
        }
        return maxflow;
    }

};
void aureg109()
{
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i] >> c[i];
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u][v]=1;
    }
    for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
    for (int i=1;i<=n;i++) a2[newnode[i]]+=a[i],b2[newnode[i]]+=b[i],c2[newnode[i]]+=c[i];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) if (adj[i][j]&&newnode[i]!=newnode[j]) haveedge[newnode[i]][newnode[j]]=1;
    ll res=0ll;
    Dinic F(nnode*nnode+nnode+1,0,nnode*nnode+nnode+1);
    for (int i=1;i<=nnode;i++)
        for (int j=1;j<=nnode;j++)
        {   
            F.add_edge(0,(i-1)*nnode+j,a2[i]*b2[j]);
            res+=a2[i]*b2[j];
            F.add_edge((i-1)*nnode+j,nnode*nnode+i,2e18);
            if (i!=j) F.add_edge((i-1)*nnode+j,nnode*nnode+j,2e18);
        }
    for (int i=1;i<=nnode;i++)
    {
        for (int j=1;j<=nnode;j++)
        if (i!=j&&haveedge[i][j]) F.add_edge(nnode*nnode+i,nnode*nnode+j,2e18);
        F.add_edge(nnode*nnode+i,nnode*nnode+nnode+1,c2[i]);
    }
    res-=F.flow();
    cout <<res;



}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    aureg109();
}