## Maximize Performance

Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

After Virat Kohli, it’s time for India to think about it’s bowlers. The team selector visits the MRF Pace academy in Chennai.

There are a total of n bowlers in the academy who are described by the number of overs they can bowl in a day. Let this be denoted by O_{i}. Owing to fatigue, there are lower and upper limits L_{i} and R_{i} for every bowler, O_{i} (both inclusive). The performance of a bowler is judged by a metric which is defined differently for every bowler by the expert. This metric is a quadratic function and performance is evaluated as f_{i}(O_{i}) where f_{i} is the function for i^{th} bowler.
There are certain relations like O_{u}<= O_{v} + d, where u and v are different bowlers and d is an integer.

The coach at the Academy wants to show that his academy is performing good, so maximize the total output of bowlers for him.

### Input

The first line of input contains integer t denoting number of testcases.

The first line of each testcase contains two integers n and m, the number of bowlers and the number of relations.

Then follow n lines, each containing three integers p_{i}, q_{i} and r_{i}, the coefficients of the quadratic function f_{i}(x). That is, f_{i}(x) = p_{i}x^{2} + q_{i}x +r_{i}

Then follow n lines, each containing l_{i} and r_{i}.

Then follow m lines, each containing three integers u_{i}, v_{i} and d_{i}, describing a relation.

### Output

For each test case, print the maximum output of all bowlers in the academy in separate line. If there is no possible combination that satisfies the constraints, output "-1".

Constraints

1<=n<=50

0<=m<=100

|p_{i}|<=10, and |q_{i}|,|r_{i}|<=1000

-100<=l_{i}<=r_{i}<=100

1<=u_{i},v_{i}<=n, u_{i} is different from v_{i}, and |d_{i}|<=200

Example

Input:

1

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

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

2 years ago

cpp

0.13 sec

660 KB

2 years ago

cpp

0.00 sec

0 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.07 sec

64 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.26 sec

656 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.11 sec

660 KB

2 years ago

cpp

0.11 sec

528 KB

2 years ago

cpp

0.11 sec

660 KB