题目描述

Bessie 正在为 Farmer John 新开的 AI 数据中心 CowWeave 设计核反应堆。

反应堆核心由 \(N\) 根燃料棒组成，编号为 \(1 \dots N\)，满足 \(1 \le N \le 2 \cdot 10^5\)。

第 \(i\) 根燃料棒有一个“稳定工作区间” \([l_i, r_i]\)，满足 \(-10^9 \le l_i \le r_i \le 10^9\)。如果 Bessie 选择的能量值 \(a_i\) 满足：

\(l_i \le a_i \le r_i\)

那么这根燃料棒就能发电；否则它虽然仍然存在，但不会发电。

注意：

• 每个 \(a_i\) 必须是整数
• \(a_i\) 可以是任意整数，不一定限制在 \([-10^9,10^9]\) 中

此外，燃料棒之间存在量子耦合，给出 \(M\) 个约束。每个约束是一个三元组 \((x,y,z)\)，表示必须满足：

\(a_x + a_y = z\)

其中 \(1 \le x,y \le N\)，\( -10^9 \le z \le 10^9\)。如果无法满足所有这些约束，反应堆就会熔毁。

请你求出：在满足全部约束的前提下，最多有多少根燃料棒能够发电。

输入格式

第一行包含整数 \(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。

否则输出一个整数，表示最多能发电的燃料棒数量。

样例 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 + a_1 = 2\)
• \(a_2 + a_2 = 10\)

如果取 \(a=[1,5,3]\)，那么共有 \(2\) 根燃料棒能发电，因为：

• \(1 \le a_1 = 1 \le 1\)
• \(3 \le a_3 = 3 \le 3\)

并且该数组满足全部约束。

样例 2

输入

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

输出

3

说明

取 \(a=[10,-10,10]\) 时，三根燃料棒都能发电。

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

数据范围

• 输入 4：所有约束都满足 \(x = y\)
• 输入 5-7：所有约束都满足 \(|x-y| = 1\)
• 输入 8-10：所有约束都满足 \(|x-y| \le 1\)
• 输入 11-13：无额外条件

命题信息

原题命题：Akshaj Arora