Zayin 有 $n$ 个元素（编号为 $1$ 到 $n$）和 $m$ 个道具（编号为 $1$ 到 $m$）。每个道具可以移除某些特定的元素。道具 $i$ 拥有护盾值 $a_i$、基础生命值 $b_i$ 和额外生命值 $c_i$。当 Zayin 想要移除一个元素时，他必须遵守以下规则：

Zayin 应该选择一个存活的道具（例如道具 $i$），该道具必须能够移除此元素。（当道具的护盾值、基础生命值和额外生命值之和严格大于 $0$ 时，道具 $i$ 是存活的。即 $a_i + b_i + c_i > 0$。）

1. 如果护盾值 ($a_i$) 大于 $0$，则护盾值减 $1$，然后跳转至第 $4$ 步；否则跳转至第 $2$ 步。
2. 如果基础生命值 ($b_i$) 大于 $0$，则基础生命值减 $0.5$，然后跳转至第 $4$ 步；否则跳转至第 $3$ 步。
3. 额外生命值 ($c_i$) 减 $1$，然后跳转至第 $4$ 步。
4. 移除该元素，过程结束。

现在 Zayin 想要移除所有元素，并最大化 $\sum_{i=1}^m \lfloor b_i + c_i \rfloor$（$\lfloor x \rfloor$ 表示向下取整，即不超过 $x$ 的最大整数）。但他太忙了，所以现在由你来解决这个问题。

输入格式

第一行包含一个整数 $T(1 \le T \le 5)$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n(1 \le n \le 100)$，表示元素的数量。 第二行包含一个整数 $m(1 \le m \le 20)$，表示道具的数量。 接下来的 $m$ 行中，第 $i$ 行首先包含三个整数 $a_i, b_i, c_i$ ($a_i, b_i, c_i \ge 0, a_i + b_i + c_i \le 10$)，分别表示道具 $i$ 的护盾值、基础生命值和额外生命值。随后是一个整数 $t_i$，表示该道具可以移除的元素数量。之后是 $t_i$ 个数字，表示这些元素的编号。

输出格式

对于每个测试用例，输出最大的 $\sum_{i=1}^m \lfloor b_i + c_i \rfloor$。（如果无法移除所有元素，则输出 “-1”）

样例

输入 1

2
5
2
2 3 1 2 3 1
1 1 1 3 4 5 2
5
2
2 3 1 1 3
1 0 1 2 1 2

输出 1

5
-1