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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct node {
  node *next;
  int where, ll, idx;
} * first[20001], a[1000001];
const int oo = 1 << 30, Max = 10000000;
int len, ans, n, m, l, dist[20001], pre[20001], way[20001], c[20001], e[51][3],
    r[51][2], init[51], fin[51], S, T;
int calc(int i, int j) { return e[i][0] * j * j + e[i][1] * j + e[i][2]; }
inline void makelist(int x, int y, int z) {
  a[++l].where = y;
  a[l].ll = z;
  a[l].idx = l;
  a[l].next = first[x];
  first[x] = &a[l];
}
bool check(int S, int T) {
  memset(dist, 0, sizeof(dist));
  dist[S] = 1;
  c[1] = S;
  for (int k = 1, l = 1; l <= k; l++) {
    int m = c[l];
    if (m == T) {
      len = dist[m] + 1;
      return true;
    }
    for (node *x = first[m]; x; x = x->next)
      if (!dist[x->where] && x->ll) {
        dist[x->where] = dist[m] + 1;
        c[++k] = x->where;
      }
  }
  return false;
}
inline void dinic(int now, int S, int T) {
  if (now == T) {
    int Minflow = oo;
    for (; now != S; now = pre[now]) Minflow = min(Minflow, a[way[now]].ll);
    ans += Minflow;
    for (now = T; now != S; now = pre[now]) {
      a[way[now]].ll -= Minflow;
      if (!a[way[now]].ll) len = dist[now];
      a[way[now] ^ 1].ll += Minflow;
    }
    return;
  }
  for (node *x = first[now]; x; x = x->next)
    if (x->ll && dist[now] + 1 == dist[x->where]) {
      pre[x->where] = now;
      way[x->where] = x->idx;
      dinic(x->where, S, T);
      if (dist[now] >= len) return;
      len = dist[T] + 1;
    }
  dist[now] = -1;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
  for (int i = 1; i <= n; i++) scanf("%d%d", &r[i][0], &r[i][1]), --r[i][0];
  memset(first, 0, sizeof(first));
  l = 1;
  S = 0;
  T = 0;
  for (int i = 1; i <= n; i++) {
    init[i] = T + 1;
    T += r[i][1] - r[i][0] + 1;
    fin[i] = T;
  }
  ++T;
  for (int i = 1; i <= n; i++) {
    makelist(S, init[i], 1 << 30);
    makelist(init[i], S, 0);
    for (int j = init[i], k = r[i][0]; k < r[i][1]; k++, j++)
      makelist(j, j + 1, Max - calc(i, k + 1)), makelist(j + 1, j, 0);
    makelist(fin[i], T, 1 << 30);
    makelist(T, fin[i], 0);
  }
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    for (int j = r[x][0]; j < r[x][1]; j++)
      if (j - z >= r[y][0] && j - z <= r[y][1])
        makelist(init[x] + j - r[x][0], init[y] + j - z - r[y][0], 1 << 30),
            makelist(init[y] + j - z - r[y][0], init[x] + j - r[x][0], 0);
  }
  ans = 0;
  for (; check(S, T); dinic(S, S, T))
    ;
  printf("%d\n", Max * n - ans);
}