题目描述

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 能够实现的最大产生动力的燃料棒数量。

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

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

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

提示

在第二个测试用例中，约束要求：

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 完成