小塔的养成游戏之梦

Problem Description

近日小塔十分热衷于各种养成类游戏，立志成为养成类游戏大手子。这天晚上，她和往常一样结束了一局养成之后上床进入了梦乡~ 俗话说日有所思梦有所想。在梦中，她依然进行着养成游戏，这次的游戏目标是——培育一个角色并尽可能在最后的比武大会上获得尽可能高的分数。角色有 $n$ 个属性，每个属性 $A_i$ 是 $0$ 到 $K$ 的一个整数。最后的比武大会上有$n-1$个评委团，每一个评委团又由若干个评委组成。每个评委都有各自的评判标准，当你达成了这个评委的评判标准，你就能获得这个评委的评分，评委的评判标准格式如下，可以由一个整数七元组 $(\text{op} , i , j , a , b , d , v)$ 表示。对于同一组的评委而言其中的$(i,j)$都是相同的。 当 op 为 0 时，代表你的角色满足 $a\times A_i+b\times A_j\leq d$ 时你就可以获得 $v$ 的评分。 当 op 为 1 时，代表你的角色满足 $a\times A_i+b\times A_j\geq d$ 时你就可以获得 $v$ 的评分。 由于评委们也不想让自己的评分规则太麻烦，所以这里的$a,b$满足$-1\leq a,b \leq 1$。 当 $i$ 和 $j$ 出现在同一个评委的评判标准中时，我们称属性 $A_i$ 和属性 $A_j$ 有关系，由于小塔的大脑比较摸鱼，不支持太高端的规则，所以最多只有一个属性会和超过一个属性有关系。比如在 $n=5$ 的情况下，假设我们用 $(1,3)$ 来表示属性 $A_1$ 和属性 $A_3$ 有关系，那么 $\{(1,2),(1,3),(1,4),(1,5)\}$ 就是一个合法的关系集合，$\{(1,2),(2,3),(2,4),(1,5)\}$ 就不是一个合法的关系集合（属性 $A_1$ 和属性 $A_2$ 都和超过一个属性有关系） 梦醒之后，小塔觉得这个游戏十分有意思，她想问问你，如果你能控制养成的角色的各个属性的值，那么最高能在比武大会上获得多少评分。

Input

第一行一个整数$T$（ $1 \le T \le 20$ )，表示数据组数。 每组数据第一行两个整数 $n,K$ ($2 \le n \le 300,1 \le K \le 10^6$)。 接着有 $n-1$ 组评委团的信息，每组信息第一行为 $x,y,cnt$ ($1 \leq x,y \le n,0 \le cnt \le 20 ,x \neq y$) 表示这个评委团里有$cnt$个评委，他们都满足 $i=x,j=y$。 接下来有 $cnt$ 行，每行有五个整数 $op,a,b,d,v$，表示这个评委团中每个评委的评判标准。其中每个参数的具体限制如下：

$$(op\in \{0,1\},-1 \leq a,b \leq 1,-10^6 \leq d \leq 10^6,-10^8 \leq v \leq 10^8) $$

Output

对于每组数据输出一个整数代表可以获得的最高评分

Sample Input

2
3 5
3 1 3
0 1 -1 0 4
0 1 1 2 2
0 1 0 1 3
3 2 2
1 1 1 2 0
1 1 -1 1 3
3 5
3 1 2
1 -1 0 3 -5
1 0 0 1 7
3 2 2
0 0 -1 3 -3
1 -1 -1 0 8

Sample Output

12
5

Hint

在第一个样例里，我们培养的角色属性为 $A_1=1 , A_2=0 , A_3=1$ 时，可以获得 12 分。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）