当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小塔最近在玩一款培育养成类游戏，她培育的角色有 $n$ 个属性，每个属性 $A_i$ 是 $0$ 到 $K$ 的一个整数。这个游戏的终极目标是在最后的展示大会上获得最高的评分，最后的展示大会上有一些评委，每个评委都有各自的评判标准，当你达成了这个评委的评判标准，你就能获得这个评委的评分，评委的评判标准格式如下，可以由一个整数七元组 $(i, j, 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 \leq n \leq 6, 1 \leq m \leq 100, 1 \leq K \leq 8)$。

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

• $op \in \{0, 1\}$
• $1 \leq i, j \leq n, i \neq j$
• $-1 \leq a, b \leq 1$
• $-10 \leq d \leq 10$
• $0 \leq v \leq 10^8$

输出格式

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

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

12

解释 #1

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

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

13