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

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

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

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