Maximum Matching

题意翻译

### 题目大意： 给你$n$个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值 你可以将一个色块翻转，例如$[col1\mid val\mid col2]->[col2\mid val\mid col1]$ 如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为构成ta的色块值的和，求所有情况下所有序列的最大值 ### 输入格式： 第一行一个整数$n$ 以下$n$行每行3个整数，表示$col1,val,col2$ ### 输出格式： 一个整数，表示最大值 ``` ### 题目大意： 给你$n$个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值 你可以将一个色块翻转，例如$[col1\mid val\mid col2]->[col2\mid val\mid col1]$ 如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为构成ta的色块值的和，求所有情况下所有序列的最大值 ### 输入格式： 第一行一个整数$n$ 以下$n$行每行3个整数，表示$col1,val,col2$ ### 输出格式： 一个整数，表示最大值 ```

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

63

输入样例 #2

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

输出样例 #2

300000

输入样例 #3

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

输出样例 #3

1000

说明

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.

题意翻译

### 题目大意： 给你$n$个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值 你可以将一个色块翻转，例如$[col1\mid val\mid col2]->[col2\mid val\mid col1]$ 如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为构成ta的色块值的和，求所有情况下所有序列的最大值 ### 输入格式： 第一行一个整数$n$ 以下$n$行每行3个整数，表示$col1,val,col2$ ### 输出格式： 一个整数，表示最大值 ``` ### 题目大意： 给你$n$个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值 你可以将一个色块翻转，例如$[col1\mid val\mid col2]->[col2\mid val\mid col1]$ 如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为构成ta的色块值的和，求所有情况下所有序列的最大值 ### 输入格式： 第一行一个整数$n$ 以下$n$行每行3个整数，表示$col1,val,col2$ ### 输出格式： 一个整数，表示最大值 ```