A11984 | 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.

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.