养成游戏

题目描述:

小塔最近在玩一款培育养成类游戏，她培育的角色有 \(n\) 个属性，每个属性 \(A_i\) 是 \(0\) 到 \(K\) 的一个整数。这个游戏的终极目标是在最后的展示大会上获得最高的评分，最后的展示大会上有一些评委，每个评委都有各自的评判标准，当你达成了这个评委的评判标准，你就能获得这个评委的评分，评委的评判标准格式如下，可以由七个整数 \((i , j , \text{op} , a , b , d , v)\) 表示。

当 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\)。

如果小塔能控制她养成的角色的属性的值，现在她问你她最高能在展示大会上获得多少评分呢？

输入格式:

第一行三个整数 \(n,m,K\) (\(2 \le n \le 6,1\le m \le 100,1 \le K \le 8\))。

接着有 \(m\) 行，每行有七个整数 \(i,j,op,a,b,d,v\)，表示一组评委的评判标准。其中每个参数的具体限制如下：

• \(op\in {0,1}\)

• \(1 \le i,j \le n,i \neq j\)

• \(-1 \leq a,b \leq 1\)

• \(-10 \leq d \leq 10\)

• \(0 \leq v \leq 10^8\)

输出格式:

输出一个整数代表她可以获得的最高评分。

样例输入:

样例1：
3 5 5
3 1 0 1 -1 0 4
3 1 0 1 1 2 2
3 1 0 1 0 1 3
3 2 1 1 1 2 0
3 2 1 1 -1 1 3

样例2：
3 5 5
1 2 1 -1 0 0 0
3 2 1 0 -1 3 2
2 3 0 -1 -1 0 4
3 1 1 1 0 0 0
1 3 0 0 1 2 9

样例输出:

样例1：
12

样例2：
13

提示:

在第一个样例里，小塔培养的角色属性为 \(A_1=1 , A_2=0 , A_3=1\) 时，可以获得 12 分。

时间限制: 1000ms
空间限制: 512MB

---