小塔的养成游戏之梦

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

俗话说日有所思梦有所想。在梦中，她依然进行着养成游戏，这次的游戏目标是——培育一个角色并尽可能在最后的比武大会上获得尽可能高的分数。角色有 $ 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 $ 都和超过一个属性有关系）

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

第一行一个整数$ 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) $$

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

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 分。

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