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.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		if (new File("input.txt").exists())
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		if (new File("output.txt").exists())
			out = new PrintWriter("output.txt");
		else
			out = new PrintWriter(System.out);

		solve();

		in.close();
		out.close();
	}

	final int maxn = 51;
	final int maxm = 111;
	final int maxVertex = 50 * 250;
	final int maxEdges = 1000 * 1000 + 10;
	final long maxVal = 1000 * 1000 * 10;
	final long inf = Long.MAX_VALUE / 4 - 1;

	int n, m;
	int s, t;
	int a[] = new int[maxn];
	int b[] = new int[maxn];
	int c[] = new int[maxn];
	int l[] = new int[maxn];
	int r[] = new int[maxn];
	int u[] = new int[maxm];
	int v[] = new int[maxm];
	int d[] = new int[maxm];

	int first[] = new int[maxn];

	int cnt = 0;
	int head[] = new int[maxVertex];
	int next[] = new int[maxEdges];
	int to[] = new int[maxEdges];
	long capacity[] = new long[maxEdges];
	long flow[] = new long[maxEdges];

	int timer;
	int used[] = new int[maxVertex];
	int cntEdges;
	int edges[] = new int[maxVertex];

	int getVertex(int v, int x) {
		if (x < l[v] - 1 || x > r[v])
			return -1;
		return first[v] + x - l[v] + 1;
	}

	void add(int u, int v, long c) {
		to[cnt] = v;
		capacity[cnt] = c;
		next[cnt] = head[u];
		head[u] = cnt++;

		to[cnt] = u;
		next[cnt] = head[v];
		head[v] = cnt++;
	}

	long f(int v, int x) {
		return a[v] * x * x + b[v] * x + c[v];
	}

	boolean push(int v, long f) {
		if (v == t)
			return true;

		used[v] = timer;

		for (int i = head[v]; i > -1; i = next[i])
			if (used[to[i]] != timer) {
				long curF = capacity[i] - flow[i];
				if (curF >= f) {
					edges[cntEdges++] = i;
					if (push(to[i], f))
						return true;
					cntEdges--;
				}
			}

		return false;
	}

	void solve() throws IOException {
		n = nextInt();
		m = nextInt();
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
			b[i] = nextInt();
			c[i] = nextInt();
		}
		for (int i = 0; i < n; i++) {
			l[i] = nextInt();
			r[i] = nextInt();
		}
		for (int i = 0; i < m; i++) {
			u[i] = nextInt() - 1;
			v[i] = nextInt() - 1;
			d[i] = nextInt();
		}

		first[0] = 1;
		for (int i = 0; i < n - 1; i++) {
			int need = r[i] - l[i] + 2;
			first[i + 1] = first[i] + need;
		}
		s = 0;
		t = first[n - 1] + r[n - 1] - l[n - 1] + 2;

		fill(head, -1);
		for (int v = 0; v < n; v++) {
			add(s, getVertex(v, l[v] - 1), inf);
			for (int f = l[v]; f <= r[v]; f++)
				add(getVertex(v, f - 1), getVertex(v, f), maxVal - f(v, f));
			add(getVertex(v, r[v]), t, inf);
		}
		for (int i = 0; i < m; i++) {
			for (int f = l[u[i]] - 1; f <= r[u[i]]; f++) {
				// int toVertex = getVertex(v[i], f - d[i]);
				// if (toVertex != -1)
				// add((getVertex(v[i], f)), toVertex, inf);
				if (l[v[i]] <= f - d[i] && f - d[i] <= r[v[i]])
					add(getVertex(u[i], f), getVertex(v[i], f - d[i]), inf);
			}
		}

		long c = 0;
		for (long f = (1l << 60); f > 0; f >>= 1) {
			timer++;
			cntEdges = 0;

			while (push(s, f)) {
				c += f;

				for (int i = 0; i < cntEdges; i++) {
					flow[edges[i]] += f;
					flow[edges[i] ^ 1] -= f;
				}

				timer++;
				cntEdges = 0;
			}
		}

		long ans = maxVal * n - c;
		out.println(ans);
	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

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

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

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

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String str = in.readLine();
			if (str == null)
				return true;
			st = new StringTokenizer(str);
		}
		return false;
	}

}