Problem Description

Bessie is designing a nuclear reactor to power Farmer John's lucrative new AI data center business, CowWeave!

The reactor core consists of $N$ ($1\le N \le 2\cdot 10^5$) fuel rods, numbered $1$ through $N$. The $i$-th rod has a "stable operating range" $[l_i, r_i]$ ($-10^9 \leq l_i \leq r_i \leq 10^9$), meaning it can only generate power if its energy $a_i$ (chosen by Bessie) satisfies $l_i \le a_i \le r_i$; otherwise, it sits idle and does not generate power. Moreover, $a_i$ must always be an integer. Note that $a_i$ can be any integer, not limited to $[-10^9, 10^9]$.

However, quantum interactions between the rods mean that there are $M$ constraints of the form $(x, y, z)$ where Bessie must satisfy $a_x + a_y = z$ ($1 \leq x,y \leq N$ and $-10^9\le z\le 10^9$) to prevent the reactor from melting down.

Help Bessie find the maximum number of power-generating rods she can achieve in her design without it melting down!

Input Format

The first line contains $T$ ($1\le T\le 10$), the number of independent tests. Each test is specified in the following format:

• The first line contains the two integers $N$ and $M$.
• The second line contains the $N$ integers $l_1, \dots, l_N$.
• The third line contains the $N$ integers $r_1, \dots, r_N$.
• The next $M$ lines each contain three integers $x$, $y$, and $z$, each representing a constraint.

It is guaranteed that neither the sum of $N$ nor the sum of $M$ over all tests exceeds $4\cdot 10^5$.

Output Format

If no choice of rod energies exists that satisfies all constraints, output $-1$. Otherwise, output the maximum number of power-generating rods Bessie can achieve.

2
3 3
1 2 3
1 2 3
1 1 2
2 2 10
1 1 4
3 2
1 2 3
1 2 3
1 1 2
2 2 10

-1
2

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0

3

5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 2

2
-1
1
-1
1

Hint

In the second test, the constraints require that:

1. $a_1 + a_1 = 2$
2. $a_2 + a_2 = 10$

Choosing energies $a=[1, 5, 3]$ results in $2$ power-generating rods because:

• $l_1 = 1 \leq a_1 \leq 1 = r_1$
• $l_3 = 3 \leq a_3 \leq 3 = r_3$

and $a$ satisfies all required constraints.

Choosing rod energies $a=[10, -10, 10]$ results in $3$ power-generating rods.

• Input 4: $x = y$ for all constraints.
• Inputs 5-7: $|x-y|=1$ for all constraints.
• Inputs 8-10: $|x-y|\le 1$ for all constraints.
• Inputs 11-13: No additional conditions.