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.io.*;
import java.util.*;


public class Main implements Runnable {

	public void _main() throws IOException {
		final int BIG = 10000000;
		int n = nextInt();
		int m = nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
			b[i] = nextInt();
			c[i] = nextInt();
		}
		int[] l = new int[n];
		int[] r = new int[n];
		int maxLen = 0;
		for (int i = 0; i < n; i++) {
			l[i] = nextInt();
			r[i] = nextInt();
			maxLen = Math.max(maxLen, r[i] - l[i] + 1);
		}
		Graph g = new Graph(n * (maxLen + 1) + 2, 2 * (n * (maxLen + 3) + m * (maxLen + 1)));
		for (int i = 0; i < n; i++) {
			int v = i * (maxLen + 1);
			g.addEdge(g.s, v, g.infinity);
			for (int x = l[i]; x <= r[i]; x++) {
				int j = x - l[i];
				int k = x - l[i] + 1;
				g.addEdge(v + j, v + k, BIG - (a[i]*x*x + b[i]*x + c[i]));
			}
			g.addEdge(v + (r[i] - l[i] + 1), g.t, g.infinity);
		}
		for (int it = 0; it < m; it++) {
			int v1 = nextInt() - 1;
			int v2 = nextInt() - 1;
			int d = nextInt();
			int v = v1 * (maxLen + 1);
			int u = v2 * (maxLen + 1);
			for (int x = l[v1] - 1; x <= r[v1]; x++) {
				if (x - d < l[v2] - 1 || x - d > r[v2]) {
					continue;
				}
				int i = x - l[v1] + 1;
				int j = x - d - l[v2] + 1;
				g.addEdge(v + i, u + j, g.infinity);
			}
		}
		out.println(n * BIG - g.minCut());
	}

	class Graph {
		final int infinity = 1000000000;

		int n, s, t;

		int[] firstEdge;
		int[] nextEdge;
		int[] edgeDst;
		int[] edgeCap;
		int[] edgeFlow;
		int numEdges;

		int[] level;
		int[] q;
		int[] lastEdge;
		boolean[] was;

		Graph(int n, int maxEdges) {
			this.n = n;
			s = n - 1;
			t = n - 2;
			firstEdge = new int[n];
			nextEdge = new int[maxEdges];
			edgeDst = new int[maxEdges];
			edgeCap = new int[maxEdges];
			edgeFlow = new int[maxEdges];
			numEdges = 0;
			level = new int[n];
			q = new int[n];
			lastEdge = new int[n];
			was = new boolean[n];
			Arrays.fill(firstEdge, -1);
		}

		void addEdge(int a, int b, int cap) {
			int e = numEdges++;
			nextEdge[e] = firstEdge[a];
			firstEdge[a] = e;
			edgeDst[e] = b;
			edgeCap[e] = cap;
			edgeFlow[e] = 0;

			e = numEdges++;
			nextEdge[e] = firstEdge[b];
			firstEdge[b] = e;
			edgeDst[e] = a;
			edgeCap[e] = 0;
			edgeFlow[e] = 0;
		}

		int minCut() {
			return maxFlow();
		}

		int maxFlow() {
			int flow = 0;
			while (bfs()) {
				for (int i = 0; i < n; i++) {
					lastEdge[i] = firstEdge[i];
				}
				while (true) {
					Arrays.fill(was, false);
					int add = dfs(s, infinity);
					if (add == 0) {
						break;
					}
					flow += add;
				}
			}
			return flow;
		}

		int dfs(int v, int by) {
			if (v == t) {
				return by;
			}
			if (was[v]) {
				return 0;
			}
			was[v] = true;
			for (; lastEdge[v] >= 0; lastEdge[v] = nextEdge[lastEdge[v]]) {
				int e = lastEdge[v];
				int u = edgeDst[e];
				if (level[u] != 1 + level[v]) {
					continue;
				}
				int nby = Math.min(by, edgeCap[e] - edgeFlow[e]);
				if (nby <= 0) {
					continue;
				}
				int x = dfs(u, nby);
				if (x > 0) {
					edgeFlow[e] += x;
					edgeFlow[e ^ 1] -= x;
					return x;
				}
			}
			return 0;
		}

		boolean bfs() {
			Arrays.fill(level, -1);
			q[0] = s;
			level[s] = 0;
			int qt = 0;
			int qh = 1;
			while (qt < qh) {
				int v = q[qt++];
				for (int e = firstEdge[v]; e >= 0; e = nextEdge[e]) {
					int u = edgeDst[e];
					if (edgeFlow[e] < edgeCap[e] && level[u] < 0) {
						level[u] = level[v] + 1;
						q[qh++] = u;
					}
				}
			}
			return level[t] >= 0;
		}
	}


	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;

	private String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String rl = in.readLine();
			if (rl == null)
				return null;
			st = new StringTokenizer(rl);
		}
		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.UK);
		new Thread(new Main()).start();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			//in = new BufferedReader(new FileReader("a.in"));
			//out = new PrintWriter(new FileWriter("a.out"));

			_main();

			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(202);
		}
	}

}