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>
inline int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
namespace Network {
const int inf = 1073741823;
static const int N = 20010, M = 1000010;
int dis[N], pre[N], vis[N], flo[N], que[N * 10];
int tot = 1, fir[N], nex[M], got[M], tak[M], cst[M];
inline void clear() {
  tot = 1;
  memset(fir, 0, sizeof(fir));
}
inline void AddEdge(int u, int v, int t, int w = 0) {
  nex[++tot] = fir[u], fir[u] = tot, got[tot] = v, tak[tot] = t, cst[tot] = w;
  nex[++tot] = fir[v], fir[v] = tot, got[tot] = u, tak[tot] = 0, cst[tot] = -w;
}
inline int bfs(int s, int t) {
  for (int i = 1; i <= t; ++i) dis[i] = 0;
  int l = 1, r = 1;
  dis[que[1] = s] = 1;
  while (l <= r) {
    int u = que[l++];
    for (int i = fir[u]; i; i = nex[i]) {
      if (dis[got[i]] || !tak[i]) continue;
      dis[got[i]] = dis[u] + 1, que[++r] = got[i];
    }
  }
  return dis[t];
}
inline int dfs(int u, int t, int flow) {
  int rest = flow;
  if (u == t) return flow;
  for (int i = fir[u]; i && rest; i = nex[i]) {
    if (dis[u] + 1 != dis[got[i]] || !tak[i]) continue;
    int tmp = dfs(got[i], t, std::min(tak[i], rest));
    if (!tmp) dis[got[i]] = 0;
    tak[i] -= tmp, tak[i ^ 1] += tmp, rest -= tmp;
  }
  return flow - rest;
}
inline int Maxflow(int s, int t) {
  int flow = 0;
  while (bfs(s, t)) flow += dfs(s, t, inf);
  return flow;
}
inline int spfa(int s, int t) {
  for (int i = 1; i <= t; i++) dis[i] = inf;
  int l = 1, r = 1;
  dis[s] = 0, flo[s] = inf, que[1] = s;
  while (l <= r) {
    int u = que[l++];
    vis[u] = false;
    for (int i = fir[u]; i; i = nex[i]) {
      int v = got[i], w = cst[i];
      if (!tak[i] || dis[u] + w >= dis[v]) continue;
      dis[v] = dis[u] + w, pre[v] = i;
      flo[v] = std::min(flo[u], tak[i]);
      if (!vis[v]) vis[v] = true, que[++r] = v;
    }
  }
  return dis[t] != inf;
}
inline std::pair<int, int> MincostMaxflow(int s, int t) {
  int cost = 0, flow = 0;
  while (spfa(s, t)) {
    cost += flo[t] * dis[t], flow += flo[t];
    for (int u = t; u != s; u = got[pre[u] ^ 1])
      tak[pre[u]] -= flo[t], tak[pre[u] ^ 1] += flo[t];
  }
  return std::make_pair(flow, cost);
}
}  // namespace Network
using namespace Network;
std::map<std::pair<int, int>, int> Map;
int a[N], b[N], c[N], l[N], r[N], cnt;
inline int idx(int a, int b) {
  return Map.find(std::make_pair(a, b)) != Map.end()
             ? Map[std::make_pair(a, b)]
             : Map[std::make_pair(a, b)] = ++cnt;
}
inline int f(int i, int x) { return a[i] * x * x + b[i] * x + c[i]; }
int main() {
  int n = read(), m = read(), Max = 2e6 + 10, s = 1e4 + 1, t = 1e4 + 2;
  for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), c[i] = read();
  for (int i = 1; i <= n; ++i) l[i] = read(), r[i] = read();
  for (int i = 1; i <= n; ++i) {
    AddEdge(s, idx(i, l[i] - 1), inf);
    for (int t = l[i]; t <= r[i]; ++t)
      Network::AddEdge(idx(i, t - 1), idx(i, t), Max - f(i, t));
    AddEdge(idx(i, r[i]), t, inf);
  }
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read(), d = read();
    for (int t = std::max(l[u], l[v] + d) - 1; t <= std::min(r[u], r[v] + d);
         ++t)
      Network::AddEdge(idx(u, t), idx(v, t - d), inf);
  }
  std::cout << n * Max - Network::Maxflow(s, t) << std::endl;
  return 0;
}