Calabash 正在他的电脑上玩一款 RPG 游戏。在这个游戏中，有 $n$ 个未知数 $x_1, x_2, \dots, x_n$ 和 $m$ 个出售提示的 NPC。第 $i$ 个 NPC 出售 $c_i$ 个提示。每个提示包含三个整数 $l_j, r_j$ 和 $w_j$，这意味着 Calabash 可以支付 $w_j$ 个金币购买该提示，该提示可以告诉 Calabash $x_{l_j} + x_{l_j+1} + \dots + x_{r_j-1} + x_{r_j}$ 的值。

游戏的目标是求出所有 $n$ 个未知数。聪明的 Calabash 知道如何最优地购买提示，但 NPC 很贪婪：对于第 $i$ 个 NPC，Calabash 必须从他那里恰好购买 $k_i$ 个提示。注意，单个提示不能被购买超过一次。

这个问题对 Calabash 来说非常困难。请编写一个程序，帮助 Calabash 找到他为了求出所有数字所需支付的最少金币数量，或者确定这是不可能的。

输入格式

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

在每个测试用例中，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 80$)，分别表示未知数的数量和 NPC 的数量。

接下来是 $m$ 个部分。每个部分以一行包含两个整数 $c_i$ 和 $k_i$ ($1 \le k_i \le c_i$) 开始，表示第 $i$ 个 NPC 拥有的提示数量以及对第 $i$ 个 NPC 的购买限制。

接下来的 $c_i$ 行，每行包含三个整数 $l_j, r_j$ 和 $w_j$ ($1 \le l_j \le r_j \le n, 1 \le w_j \le 10^6$)，描述了第 $i$ 个 NPC 提供的提示。

保证在每个测试用例中，所有 $c_i$ 的总和最多为 80。

输出格式

对于每个测试用例，打印一行，包含一个整数，表示最少的金币数量。如果无解，则输出 “-1”。

样例

输入 1

2
2 2
1 1
1 2 1
3 2
1 1 10
2 2 100
1 2 1000
2 2
1 1
1 1 1
1 1
1 1 2

输出 1

111
-1