Maximum Matching

Description:

Input:

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

Output:

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

Sample Input:

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

Sample Output:

63

Sample Input:

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

Sample Output:

300000

Sample Input:

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

Sample Output:

1000

Note:

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.