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!

Problem credits: Akshaj Arora

SCORING

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

Problem credits: Akshaj Arora

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.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver