你有$$$n$$$块,每个块的形式为[color$$$_1$$$|value|color$$$_2$$$],其中块也可以翻转得到[color$$$_2$$$|value|color$$$_1$$$]。
如果相邻块的接触端点具有相同的颜色,则块序列被称为有效。例如,如果 B 的左侧颜色与 A 的右侧颜色相同,并且 B 的右侧颜色与 C 的左侧颜色相同,则三个块 A、B 和 C 的序列有效。
序列的值定义为该序列中块的值的总和。
找到可以从给定块的子集构造的有效序列的最大可能值。如有必要,可以对子集中的块进行重新排序和翻转。每个块在序列中最多可以使用一次。
输入
输入的第一行包含一个整数 $$$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{颜色}_{2,i} \le 4$$$, $$$1 \le \mathrm{值}_i \le 100\,000$$$)。
输出
精确打印一个整数——块子集的最大总值,这构成了一个有效的序列。
示例
输入 #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
注意
在第一个示例中,可以从所有块形成有效序列。
有效序列之一如下:
[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]
在第三个示例中,不可能形成两个或多个块的有效序列,因此答案是仅由第一个块组成的序列,因为它是具有最大值的块。