Problems
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≤N≤2⋅10^5) fuel rods, numbered 1 through N. The i-th rod has a "stable operating range" [li,ri](−10^9≤li≤ri≤10^9), meaning it can only generate power if its energy ai(chosen by Bessie) satisfies li≤ai≤ri; otherwise, it sits idle and does not generate power. Moreover, aimust always be an integer. Note that aican be any integer, not limited to [−10^9,10^9].
However, quantum interactions between the rods mean that there are Mconstraints of the form (x,y,z)where Bessie must satisfy ax+ay=z(1≤x,y≤Nand −10^9≤z≤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
The first line contains T (1≤T≤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 l1,…,lN.
The third line contains the N integers r1,…,rN.
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⋅10^5.
Output
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.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | x=y for all constraints |
| #2 | 20 | |x−y|=1 for all constraints. |
| #3 | 30 | |x−y|≤1 for all constraints |
| #4 | 40 | No additional conditions. |
Example #1
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
In the second test, the constraints require that:
a1+a1=2
a2+a2=10
Choosing energies a=[1,5,3] results in 2 power-generating rods because:
l1=1≤a1≤1=r1
l3=3≤a3≤3=r3
and a satisfies all required constraints.
Example #2
1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0
3
Choosing rod energies a=[10,−10,10] results in 3 power-generating rods.
Example #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
You must sign in to write code.