E. Наибольшее паросочетание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ блоков, каждый из которых выглядит как [color$$$_1$$$|value|color$$$_2$$$], при чём блок можно также перевернуть, чтобы получить [color$$$_2$$$|value|color$$$_1$$$].

Назовём последовательность блоков корректной, если касающиеся концы блоков совпадают по цветам. Например, последовательность из трёх блоков A, B и C является корректной, если левый цвет B совпадает с правым цветом A и правый цвет B совпадает с левым цветом C.

Ценность последовательности равна сумме ценностей (value) отдельных блоков в ней.

Найдите наибольшую возможную ценность корректной последовательности блоков, которую можно составить из какого-то подмножества данных блоков. Блоки в этом подмножестве можно произвольным образом перемещать и переворачивать. Каждый блок можно использовать не более одного раза в последовательности.

Входные данные

Первая строка входных данных содержит одно целое число $$$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$$$).

Выходные данные

Выведите ровно одно целое число — максимальная суммарная ценность блоков, образующих корректную последовательность.

Примеры
Входные данные
6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2
Выходные данные
63
Входные данные
7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3
Выходные данные
300000
Входные данные
4
1 1000 1
2 500 2
3 250 3
4 125 4
Выходные данные
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]

В третьем примере нельзя построить корректную последовательность содержающую два или более блока, поэтому оптимальный ответ состоит из одного первого блока, так как он имеет наибольшую ценность.