logo AlgoBeat OnlineJudge
登录 注册

#215081. [USACO26JAN1] Mooclear Reactor S

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Bessie 正在设计一个核反应堆,为 Farmer John 利润丰厚的新 AI 数据中心业务 CowWeave 提供动力!

反应堆核心由 )个燃料棒组成,编号为 。第 个燃料棒有一个“稳定工作范围” ),这意味着只有当其能量 (由 Bessie 选择)满足 时,它才能产生动力;否则,它将处于闲置状态且不产生动力。此外, 必须始终为整数。注意, 可以是任意整数,不限于

然而,燃料棒之间的量子相互作用意味着存在 个形式为 的约束,其中 Bessie 必须满足 ),以防止反应堆熔毁。

请帮助 Bessie 找到在她的设计中,在不发生熔毁的情况下,能够实现的最大产生动力的燃料棒数量!

输入格式

第一行包含 ),表示独立测试的数量。每个测试按以下格式指定:

  • 第一行包含两个整数
  • 第二行包含 个整数
  • 第三行包含 个整数
  • 接下来的 行,每行包含三个整数 ,每个表示一个约束。

保证所有测试中 的总和以及 的总和都不超过

输出格式

如果不存在任何燃料棒能量选择能满足所有约束,则输出 。否则,输出 Bessie 能够实现的最大产生动力的燃料棒数量。

样例

样例输入 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

-1
2

样例输入 2

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0

样例输出 2

3

样例输入 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

样例输出 3

2
-1
1
-1
1

数据范围与提示

在第二个测试用例中,约束要求:

选择能量 会产生 个产生动力的燃料棒,因为:

并且 满足所有必需的约束。


选择燃料棒能量 会产生 个产生动力的燃料棒。


  • 输入 :所有约束中
  • 输入 -:所有约束中
  • 输入 -:所有约束中
  • 输入 -:无附加条件。

翻译由 DeepSeek V3 完成