Problem: Nanami likes playing games, and is also really good at it. This day she was playing a new game which involved operating a power plant. Nanami's job is to control the generators in the plant and produce maximum output.

There are n generators in the plant. Each generator should be set to a generating level. Generating level is an integer (possibly zero or negative), the generating level of the i-th generator should be between li and ri (both inclusive). The output of a generator can be calculated using a certain quadratic function f(x), where x is the generating level of the generator. Each generator has its own function, the function of the i-th generator is denoted as fi(x).

However, there are m further restrictions to the generators. Let the generating level of the i-th generator be xi. Each restriction is of the form xu ≤ xv + d, where u and v are IDs of two different generators and d is an integer.

Nanami found the game tedious but giving up is against her creed. So she decided to have a program written to calculate the answer for her (the maximum total output of generators). Somehow, this became your job.

Input

The first line contains two integers n and m (1 ≤ n ≤ 50; 0 ≤ m ≤ 100) — the number of generators and the number of restrictions.

Then follow n lines, each line contains three integers ai, bi, and ci (|ai| ≤ 10; |bi|, |ci| ≤ 1000) — the coefficients of the function fi(x). That is, fi(x) = aix2 + bix + ci.

Then follow another n lines, each line contains two integers li and ri ( - 100 ≤ li ≤ ri ≤ 100).

Then follow m lines, each line contains three integers ui, vi, and di (1 ≤ ui, vi ≤ n; ui ≠ vi; |di| ≤ 200), describing a restriction. The i-th restriction is xui ≤ xvi + di.

Output

Print a single line containing a single integer — the maximum output of all the generators. It is guaranteed that there exists at least one valid configuration.

Examples

Input

3 3
0 1 0
0 1 1
0 1 2
0 3
1 2
-100 100
1 2 0
2 3 0
3 1 0


Output

9


Input

5 8
1 -8 20
2 -4 0
-1 10 -10
0 1 0
0 -1 1
1 9
1 4
0 10
3 11
7 9
2 1 3
1 2 3
2 3 3
3 2 3
3 4 3
4 3 3
4 5 3
5 4 3


Output

46

Note

In the first sample, f1(x) = x, f2(x) = x + 1, and f3(x) = x + 2, so we are to maximize the sum of the generating levels. The restrictions are x1 ≤ x2, x2 ≤ x3, and x3 ≤ x1, which gives us x1 = x2 = x3. The optimal configuration is x1 = x2 = x3 = 2, which produces an output of 9.

In the second sample, restrictions are equal to |xi - xi + 1| ≤ 3 for 1 ≤ i < n. One of the optimal configurations is x1 = 1, x2 = 4, x3 = 5, x4 = 8 and x5 = 7.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class D248 {
    public static class Edge{
        int from, to;
        int capacity, flow;
        Edge r; //keep track of reverse edge
        long cost;
        public Edge(int from, int to, int capacity, long cost){
            this.from = from;
            this.to = to;
            this.capacity = capacity;
            this.cost = cost;
        }

        public Edge(int from, int to, int capacity){
            this(from,to,capacity,1);
        }
    }
    public static class AdjList extends ArrayList<ArrayList<Edge>> {}

    AdjList adj;
    static int INF = 1<<30;
    public D248(int n){
        adj = new AdjList();
        for(int i=0;i<n;++i){
            adj.add( new ArrayList<Edge>() );
        }
    }

    //add edge without cost (0 cost)
    public void addEdge(int from, int to, int capacity){
        Edge e, r;
        e = new Edge(from, to, capacity);
        r = new Edge(to, from, 0);
        e.r = r;
        r.r = e;
        adj.get(from).add( e );
        adj.get(to).add( r );
    }
    //reconstruct path
    //convert array of parent references to a path
    public LinkedList<Edge> toPath(Edge[] parent, int s, int t){
        LinkedList<Edge> path = new LinkedList<Edge>();
        if(parent[t] == null) return null;
        int c = t;
        while(c != s){
            path.addFirst(parent[c]);
            c = parent[c].from;
        }
        return path;
    }


    //Find path using BFS
    //not for min cost max flow
    public LinkedList<Edge> findPath(int s, int t){
        int n = adj.size();
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(s);
        boolean[] visited = new boolean[n];
        Edge[] parent = new Edge[n];
        while(!q.isEmpty()){
            int u = q.poll();
            if( u == t) break;
            for(Edge e: adj.get(u)){
                int res = e.capacity - e.flow;
                if( res > 0 && !visited[e.to]){
                    parent[e.to] = e;
                    q.add(e.to);
                    visited[e.to] = true;
                }
            }
        }
        return toPath(parent, s, t);
    }

    //find and push maximum possible flow along path
    public long push(LinkedList<Edge> path){
        long f = INF;
        for(Edge e: path){
            int res = e.capacity - e.flow;
            f = Math.min(f, res);
        }
        for(Edge e: path){
            e.flow += f;
            e.r.flow -= f;
        }
        return f;
    }

    //Ford Fulkerson (Edmonds Karp variant using BFS)
    public int ff(int s, int t){
        int f= 0;
        while(true){
            LinkedList<Edge> path = findPath(s,t);
            if(path == null) break;
            f += push(path);
        }
        return f;
    }

    public static int f(int x, int i, int[] A, int[] B, int[] C){
        return A[i] * x * x + B[i] * x + C[i];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //function coefficients
        int[] A = new int[n+1];
        int[] B = new int[n+1];
        int[] C = new int[n+1];
        for(int i=1;i<=n;++i){
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
            C[i] = sc.nextInt();
        }
        int[] L = new int[n+1];
        int[] R = new int[n+1];
        int nodes = 0;
        int mv=-INF;
        int [] first = new int[n+1]; //first index of gen
        for(int i=1;i<=n;++i){
            first[i] = nodes + 1;
            L[i] = sc.nextInt();
            R[i] = sc.nextInt();
            nodes += R[i] - L[i] + 2;
            for(int x=L[i];x<=R[i];++x){
                mv = Math.max(mv, f(x,i,A,B,C));
            }
        }
        D248 F = new D248(nodes+2);
        for(int i=1;i<=n;++i){
            int s = first[i] - L[i];
            F.addEdge(0, first[i], INF);  //source to each LI
            for(int x=L[i];x<=R[i];++x){
                F.addEdge(s+x, s+x+1, mv - f(x, i, A,B,C));
            }
            F.addEdge(s+R[i]+1, nodes+1, INF); //each RI to sink
        }

        for(int i=1;i<=m;++i){
            int u = sc.nextInt();
            int v = sc.nextInt();
            int d = sc.nextInt();
            for(int j=L[u];j<=R[u];++j){
                //check restriction
                if(j>=L[v]+d && j <= R[v] + d + 1){
                    int start = first[u] - L[u] + j;
                    int end = first[v] - L[v] + j - d;
                    F.addEdge(start, end, INF);
                }
            }
        }
        System.out.println(mv *n - F.ff(0,nodes+1));



    }
}