题目描述

星港的主反应堆由 $n$ 根控制棒共同维持稳定。第 $i$ 根控制棒需要被调到一个整数能级 $a_i$。由于材料窗口限制，如果最终满足

则称第 $i$ 根控制棒处于高效状态；否则它仍可参与配平，但不能计入高效数量。注意，$a_i$ 可以是任意整数，不要求落在 $[-10^9,10^9]$ 内。

反应堆中还有 $m$ 条配平约束。每条约束形如 $(x,y,z)$，表示最终必须满足

请你判断是否存在一组整数能级满足所有配平约束。若不存在，输出 $-1$；否则，输出在满足所有约束的前提下，最多能让多少根控制棒处于高效状态。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$。
• 第二行包含 $n$ 个整数 $l_1,l_2,\ldots,l_n$。
• 第三行包含 $n$ 个整数 $r_1,r_2,\ldots,r_n$。
• 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示一条约束 $a_x+a_y=z$。

输出格式

对于每组测试数据，输出一行一个整数：

• 若不存在任何整数能级方案满足所有约束，输出 $-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
2

样例解释

第一组数据中，约束要求 $a_1=1$，$a_2=5$，同时又要求 $a_1=2$，互相矛盾，所以无解。

第二组数据中，约束要求 $a_1=1$，$a_2=5$，可以任选 $a_3$。令 $a_3=3$ 时，第 $1$ 根和第 $3$ 根控制棒处于高效状态，答案为 $2$。

数据范围

对于所有测试数据，满足：

• $1\le T\le 10$；
• $1\le n\le 2\times 10^5$；
• $0\le m\le 4\times 10^5$；
• $-10^9\le l_i\le r_i\le 10^9$；
• $1\le x,y\le n$；
• $-10^9\le z\le 10^9$；
• 所有测试数据中，$n$ 的总和与 $m$ 的总和均不超过 $4\times 10^5$。

子任务

限制

时间限制：$1\text{s}$。

空间限制：$512\text{MB}$。