P14978 [USACO26JAN1] Mooclear Reactor S

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.

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.