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

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

说明 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$ 满足所有要求的约束。

输入样例 2

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

输出样例 2

3

说明 2

选择燃料棒能量 $a=[10, -10, 10]$ 可以得到 $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

子任务

• 测试点 4：对于所有约束，满足 $x = y$。
• 测试点 5-7：对于所有约束，满足 $|x-y|=1$。
• 测试点 8-10：对于所有约束，满足 $|x-y|\le 1$。
• 测试点 11-13：无附加限制。