35324번 - Mooclear Reactor 다국어

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!

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$.

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.