养成游戏

题目描述

小塔正在玩一款养成类游戏。她培养的角色有 $n$ 个属性，每个属性 $A_i$ 都是一个 $0$ 到 $K$ 之间的整数。展示大会上有 $m$ 位评委，每位评委都有一条评分规则；如果角色满足这条规则，就能获得对应的评分。你的任务是决定所有属性的取值，使总评分最大。

每条评分规则由七个整数 $(i,j,\mathrm{op},a,b,d,v)$ 描述：

• 当 $\mathrm{op}=0$ 时，若$$a \times A_i + b \times A_j \le d$$ 则可获得 $v$ 分。
• 当 $\mathrm{op}=1$ 时，若$$a \times A_i + b \times A_j \ge d$$ 则可获得 $v$ 分。

其中参数满足 $-1 \le a,b \le 1$。请输出小塔能够获得的最高总分。

输入格式

从标准输入按以下格式读取数据：

$n$ $m$ $K$

接下来 $m$ 行，每行输入：

$i$ $j$ $\mathrm{op}$ $a$ $b$ $d$ $v$

其中：

• 第一行输入三个整数 $n,m,K$。
• 接下来 $m$ 行，每行给出一条评委规则。

输出格式

输出一个整数，表示她能够获得的最高评分。

数据范围

• $2 \le n \le 6$
• $1 \le m \le 100$
• $1 \le K \le 8$
• $\mathrm{op} \in \{0,1\}$
• $1 \le i,j \le n$ 且 $i \ne j$
• $-1 \le a,b \le 1$
• $-10 \le d \le 10$
• $0 \le v \le 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

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