绘画是一项非常浪漫的活动。在立方体上绘画则更加浪漫。而在立方体上创作艺术画作则是最浪漫的事情。

有 $N$ 个立方体排成一行，从左到右依次编号为 $1$ 到 $N$。你的任务是选择其中的一些立方体并将它们涂色。然而，为了使画作具有艺术感，你必须遵守一些规则。规则分为两类，描述如下：

1. 编号属于区间 $[L_i, R_i]$ 的已涂色立方体数量不得少于 $K_i$ 个 ($1 \le i \le M_1$)。
2. 编号不属于区间 $[L_i, R_i]$ 的已涂色立方体数量不得少于 $K_i$ 个 ($1 \le i \le M_2$)。

绘画也是一项令人疲惫的活动，因此你需要涂色的立方体数量应尽可能少。

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $N, M_1$ 和 $M_2$ ($1 \le N \le 3\,000, 0 \le M_1, M_2 \le 3\,000$)，分别表示立方体的数量、第一类规则的数量和第二类规则的数量。接下来的 $M_1$ 行，每行包含三个整数 $L_i, R_i, K_i$ ($1 \le i \le M_1, 1 \le L_i \le R_i \le N, 0 \le K_i \le R_i - L_i + 1$)，描述一条第一类规则。再接下来的 $M_2$ 行，每行包含三个整数 $L_i, R_i, K_i$ ($1 \le i \le M_2, 1 \le L_i \le R_i \le N, 0 \le K_i \le N - (R_i - L_i + 1)$)，描述一条第二类规则。

保证所有测试用例中 $N$ 的总和不超过 $3\,000$，$M_1$ 的总和与 $M_2$ 的总和也均不超过 $3\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示你需要涂色的最少立方体数量。

样例

输入 1

1
3 1 1
1 2 1
2 2 1

输出 1

1