2094: [USACO 2026 First Contest, Silver] Problem 2. 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 () fuel rods, numbered through . The -th rod has a "stable operating range" (), meaning it can only generate power if its energy (chosen by Bessie) satisfies ; otherwise, it sits idle and does not generate power. Moreover, must always be an integer. Note that can be any integer, not limited to .
However, quantum interactions between the rods mean that there are constraints of the form where Bessie must satisfy ( and ) 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 the two integers and .
- The second line contains the integers .
- The third line contains the integers .
- The next lines each contain three integers , , and , each representing a constraint.
It is guaranteed that neither the sum of nor the sum of over all tests exceeds .
输出
样例输入
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:
Choosing energies results in power-generating rods because:
and satisfies all required constraints.
SAMPLE INPUT:
1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0
SAMPLE OUTPUT:
3
Choosing rod energies results in power-generating rods.
SAMPLE INPUT:
5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 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
SAMPLE OUTPUT:
2
-1
1
-1
1
SCORING:
- Input 4: for all constraints.
- Inputs 5-7: for all constraints.
- Inputs 8-10: for all constraints.
- Inputs 11-13: No additional conditions.