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_ix² + q_ix +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