P14978 [USACO26JAN1] Mooclear Reactor S

Bessie 正在设计一个核反应堆，为 Farmer John 利润丰厚的新 AI 数据中心业务 CowWeave 提供动力！ 反应堆核心由 $N$（$1\le N \le 2\cdot 10^5$）个燃料棒组成，编号为 $1$ 到 $N$。第 $i$ 个燃料棒有一个“稳定工作范围” $[l_i, r_i]$（$-10^9 \leq l_i \leq r_i \leq 10^9$），这意味着只有当其能量 $a_i$（由 Bessie 选择）满足 $l_i \le a_i \le r_i$ 时，它才能产生动力；否则，它将处于闲置状态且不产生动力。此外，$a_i$ 必须始终为整数。**注意，$a_i$ 可以是任意整数，不限于 $[-10^9, 10^9]$。** 然而，燃料棒之间的量子相互作用意味着存在 $M$ 个形式为 $(x, y, z)$ 的约束，其中 Bessie 必须满足 $a_x + a_y = z$（$1 \leq x,y \leq N$ 且 $-10^9\le z\le 10^9$），以防止反应堆熔毁。 请帮助 Bessie 找到在她的设计中，在不发生熔毁的情况下，能够实现的最大产生动力的燃料棒数量！

第一行包含 $T$（$1\le T\le 10$），表示独立测试的数量。每个测试按以下格式指定： - 第一行包含两个整数 $N$ 和 $M$。 - 第二行包含 $N$ 个整数 $l_1, \dots, l_N$。 - 第三行包含 $N$ 个整数 $r_1, \dots, r_N$。 - 接下来的 $M$ 行，每行包含三个整数 $x$、$y$ 和 $z$，每个表示一个约束。 保证所有测试中 $N$ 的总和以及 $M$ 的总和都不超过 $4\cdot 10^5$。

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

在第二个测试用例中，约束要求： 1. $a_1 + a_1 = 2$ 2. $a_2 + a_2 = 10$ 选择能量 $a=[1, 5, 3]$ 会产生 $2$ 个产生动力的燃料棒，因为： - $l_1 = 1 \leq a_1 \leq 1 = r_1$ - $l_3 = 3 \leq a_3 \leq 3 = r_3$ 并且 $a$ 满足所有必需的约束。 --- 选择燃料棒能量 $a=[10, -10, 10]$ 会产生 $3$ 个产生动力的燃料棒。 --- - 输入 $4$：所有约束中 $x = y$。 - 输入 $5$-$7$：所有约束中 $|x-y|=1$。 - 输入 $8$-$10$：所有约束中 $|x-y|\le 1$。 - 输入 $11$-$13$：无附加条件。 翻译由 DeepSeek V3 完成