题目描述

近日小塔十分热衷于各种养成类游戏，立志成为养成类游戏大手子。这天晚上，她和往常一样结束了一局养成之后上床进入了梦乡~

俗话说日有所思梦有所想。在梦中，她依然进行着养成游戏，这次的游戏目标是——培育一个角色并尽可能在最后的比武大会上获得尽可能高的分数。角色有 $n$ 个属性，每个属性 $A_i$ 是 $0$ 到 $K$ 的一个整数。最后的比武大会上有 $n−1$ 个评委团，每一个评委团又由若干个评委组成。每个评委都有各自的评判标准，当你达成了这个评委的评判标准，你就能获得这个评委的评分，评委的评判标准格式如下，可以由一个整数七元组 $(op,i,j,a,b,d,v)$ 表示。对于同一组的评委而言其中的$(i,j)$都是相同的。

当 $op$ 为 $0$ 时，代表你的角色满足 $a×A_i+b×A_j≤d$ 时你就可以获得 $v$ 的评分。

当 $op$ 为 $1$ 时，代表你的角色满足 $a×A_i+b×A_j≥d$ 时你就可以获得 $v$ 的评分。

由于评委们也不想让自己的评分规则太麻烦，所以这里的 $a,b$ 满足 $−1≤a,b≤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$ 都和超过一个属性有关系）

梦醒之后，小塔觉得这个游戏十分有意思，她想问问你，如果你能控制养成的角色的各个属性的值，那么最高能在比武大会上获得多少评分。

输入格式

第一行一个整数 $T$（ $1≤T≤20$)，表示数据组数。

每组数据第一行两个整数 $n,K$ ($2≤n≤300,1≤K≤10^6$)。

接着有 $n−1$ 组评委团的信息，每组信息第一行为 $x,y,cnt$ ($1≤x,y≤n,0≤cnt≤20,x≠y$) 表示这个评委团里有 $cnt$ 个评委，他们都满足 $i=x,j=y$。

接下来有 $cnt$ 行，每行有五个整数 $op,a,b,d,v$，表示这个评委团中每个评委的评判标准。其中每个参数的具体限制如下：

输出格式

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

输入样例

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

输出样例

12
5

提示

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