You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 512.0 MB

# 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 Format
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 Format
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.

Now solve the problem and return the code.