CF1038E.Maximum Matching

You are given $n$ blocks, each of them is of the form [color$_1$|value|color$_2$], where the block can also be flipped to get [color$_2$|value|color$_1$].

A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.

The value of the sequence is defined as the sum of the values of the blocks in this sequence.

Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.

给你 $n$ 个方块，每个方块的形式为 [color$_1$|value|color$_2$]，其中该方块也可以被翻转，从而变为 [color$_2$|value|color$_1$]。

若一个方块序列中，相邻方块相接触的端点具有相同的颜色，则称该序列为合法序列。例如，三个方块 A、B 和 C 构成的序列是合法的，当且仅当 B 的左端颜色与 A 的右端颜色相同，且 B 的右端颜色与 C 的左端颜色相同。

该序列的值定义为序列中所有方块的 value 之和。

请从给定的方块集合中选出一个子集（可重排顺序，也可对其中任意方块进行翻转），构造出一个合法序列，使得其值最大。每个方块在序列中至多使用一次。

The first line of input contains a single integer $n$ ($1 \le n \le 100$) — the number of given blocks.

Each of the following $n$ lines describes corresponding block and consists of $\mathrm{color}_{1,i}$, $\mathrm{value}_i$ and $\mathrm{color}_{2,i}$ ($1 \le \mathrm{color}_{1,i}, \mathrm{color}_{2,i} \le 4$, $1 \le \mathrm{value}_i \le 100\,000$).

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

接下来的 $n$ 行，每行描述一个对应的方块，包含 $\mathrm{color}_{1,i}$、$\mathrm{value}_i$ 和 $\mathrm{color}_{2,i}$（其中 $1 \le \mathrm{color}_{1,i}, \mathrm{color}_{2,i} \le 4$，$1 \le \mathrm{value}_i \le 100\,000$）。

Print exactly one integer — the maximum total value of the subset of blocks, which makes a valid sequence.

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

In the first example, it is possible to form a valid sequence from all blocks.

One of the valid sequences is the following:

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

The first block from the input ([2|1|4] $\to$ [4|1|2]) and second ([1|2|4] $\to$ [4|2|1]) are flipped.

In the second example, the optimal answers can be formed from the first three blocks as in the following (the second or the third block from the input is flipped):

[2|100000|1] [1|100000|1] [1|100000|2]

In the third example, it is not possible to form a valid sequence of two or more blocks, so the answer is a sequence consisting only of the first block since it is the block with the largest value.

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

其中一个有效序列如下：

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

输入中的第一个方块（[2|1|4] $\to$ [4|1|2]）和第二个方块（[1|2|4] $\to$ [4|2|1]）被翻转了。

在第二个例子中，最优解可由输入的前三个方块构成，如下所示（输入中的第二个或第三个方块被翻转）：

[2|100000|1] [1|100000|1] [1|100000|2]

在第三个例子中，无法构成包含两个或更多方块的有效序列，因此答案仅为仅含第一个方块的序列，因为它是所有方块中数值最大的那个。