Вам даны \(n\) блоков, каждый из которых выглядит как [color\(_1\)|value|color\(_2\)], при чём блок можно также перевернуть, чтобы получить [color\(_2\)|value|color\(_1\)].
Назовём последовательность блоков корректной, если касающиеся концы блоков совпадают по цветам. Например, последовательность из трёх блоков A, B и C является корректной, если левый цвет B совпадает с правым цветом A и правый цвет B совпадает с левым цветом C.
Ценность последовательности равна сумме ценностей (value) отдельных блоков в ней.
Найдите наибольшую возможную ценность корректной последовательности блоков, которую можно составить из какого-то подмножества данных блоков. Блоки в этом подмножестве можно произвольным образом перемещать и переворачивать. Каждый блок можно использовать не более одного раза в последовательности.
Выходные данные
Выведите ровно одно целое число — максимальная суммарная ценность блоков, образующих корректную последовательность.
Примечание
В первом примере возможно составить корректную подпоследовательность из всех блоков.
Один из корректных способов следующий:
[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]
В третьем примере нельзя построить корректную последовательность содержающую два или более блока, поэтому оптимальный ответ состоит из одного первого блока, так как он имеет наибольшую ценность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2
|
63
|
|
2
|
7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3
|
300000
|
|
3
|
4
1 1000 1
2 500 2
3 250 3
4 125 4
|
1000
|