E. 最大匹配

每个测试的时间限制：2 秒
每个测试的内存限制：256 兆字节

---

题目描述

有 $n$ 个块，每个块的形式为 $[\text{color}_1 \mid \text{value} \mid \text{color}_2]$，并且该块可以翻转得到 $[\text{color}_2 \mid \text{value} \mid \text{color}_1]$。

一个块序列被称为有效的，当且仅当相邻块接触端点的颜色相同。
例如，三个块 $A$、$B$ 和 $C$ 的序列是有效的，如果 $B$ 的左侧颜色与 $A$ 的右侧颜色相同，且 $B$ 的右侧颜色与 $C$ 的左侧颜色相同。

序列的价值定义为该序列中所有块的数值之和。

请找出：从给定的块中选取一个子集，并经过重新排序和必要的翻转后，能够构成的有效序列的最大可能总价值。
每个块在序列中最多使用一次。

---

输入格式

第一行包含一个整数 $n$（$1 \le n \le 100$）—— 给定块的数量。

接下来的 $n$ 行，每行描述一个块，包含三个整数 $\text{color}_{1,i}$、$\text{value}_i$ 和 $\text{color}_{2,i}$（$1 \le \text{color}_{1,i}, \text{color}_{2,i} \le 4$，$1 \le \text{value}_i \le 10^5$）。

---

输出格式

输出一个整数 —— 能构成有效序列的块子集的最大总价值。

---

样例

样例 1

输入：

6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2

输出：

63

样例 2

输入：

7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3

输出：

300000

样例 3

输入：

4
1 1000 1
2 500 2
3 250 3
4 125 4

输出：

1000

---

提示

在第一个样例中，可以使用所有块构成一个有效序列。

其中一个有效序列如下：

$[4 \mid 2 \mid 1] \ [1 \mid 32 \mid 2] \ [2 \mid 8 \mid 3] \ [3 \mid 16 \mid 3] \ [3 \mid 4 \mid 4] \ [4 \mid 1 \mid 2]$

其中输入的第一个块 $[2 \mid 1 \mid 4]$ 被翻转为 $[4 \mid 1 \mid 2]$，第二个块 $[1 \mid 2 \mid 4]$ 被翻转为 $[4 \mid 2 \mid 1]$。

在第二个样例中，最优解可以由前三个块构成（将输入的第二或第三个块翻转）：

$[2 \mid 100000 \mid 1] \ [1 \mid 100000 \mid 1] \ [1 \mid 100000 \mid 2]$

在第三个样例中，无法构成由两个或更多块组成的有效序列，因此答案是只包含第一个块的序列，因为它是价值最大的块。