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.


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


-----Examples-----
Input
6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2

Output
63
Input
7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3

Output
300000
Input
4
1 1000 1
2 500 2
3 250 3
4 125 4

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.

Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

Complete search

Dynamic programming
Skill types: Dynamic programming

Bit manipulation

Complete search

Starter code:

Solutions:
n = int(input())
mv = 10 ** 9
f = [0 for i in range(4)]
adj = [[i == j for j in range(4)] for i in range(4)]
w = [0 for i in range(4)]
for _ in range(n):
	(a, v, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a != b:
		mv = min(mv, v)
	f[a] ^= 1
	f[b] ^= 1
	w[a] += v
	adj[a][b] = adj[b][a] = True
for k in range(4):
	for i in range(4):
		for j in range(4):
			if adj[i][k] and adj[k][j]:
				adj[i][j] = True
if all(adj[0]) and all(f):
	print(sum(w) - mv)
else:
	print(max((sum((w[j] for j in range(4) if adj[i][j])) for i in range(4))))


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, **kwargs, file=sys.stderr)
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N,) = getIntList()
zb = []
total = 0
de = [0, 0, 0, 0, 0]
gr = [[] for i in range(5)]
minv = 10000000
for i in range(N):
	(a, b, c) = getIntList()
	de[a] += 1
	de[c] += 1
	zb.append((a, b, c))
	total += b
	if a != c:
		minv = min(minv, b)
vis = [0, 0, 0, 0, 0]

def dfs(root):
	if vis[root]:
		return []
	vis[root] = 1
	r = [root]
	for x in zb:
		(a, b, c) = x
		if a == root:
			r = r + dfs(c)
		elif c == root:
			r = r + dfs(a)
	return r
res = 0
for i in range(1, 5):
	if vis[i]:
		continue
	t = dfs(i)
	t = set(t)
	if len(t) == 4:
		for j in range(1, 5):
			if de[j] % 2 == 0:
				print(total)
				sys.exit()
		print(total - minv)
		sys.exit()
	tr = 0
	for x in zb:
		(a, b, c) = x
		if a in t:
			tr += b
	res = max(res, tr)
print(res)


def min(a, b):
	if a < b:
		return a
	return b

def max(a, b):
	return abs(min(-a, -b))
been = [0 for i in range(4)]
ans = 0
minw = 10 ** 18
degpar = [0 for i in range(4)]
w = [0 for i in range(4)]
gr = [list() for i in range(4)]
rem = [[0 for i in range(4)] for j in range(4)]

def dfs(x, l):
	l.append(w[x])
	if been[x]:
		return
	been[x] = 1
	for i in gr[x]:
		if been[i] == 0 and rem[x][i] > 0:
			dfs(i, l)
n = int(input())
blocks = []
for i in range(n):
	(a, v, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a != b:
		blocks.append([a, v, b])
	w[b] += v
	if a != b:
		minw = min(minw, v)
	degpar[a] += 1
	degpar[a] %= 2
	degpar[b] += 1
	degpar[b] %= 2
	gr[a].append(b)
	gr[b].append(a)
	rem[a][b] += 1
	rem[b][a] += 1
ok = True
for i in range(4):
	l = []
	if been[i] == 0:
		dfs(i, l)
	if i == 0 and all(been) and all(degpar):
		ok = False
		break
	ans = max(ans, sum(l))
if ok:
	print(ans)
	exit()
for p in blocks:
	i = p[0]
	j = p[2]
	w[j] -= p[1]
	been = [0 for i in range(4)]
	rem[i][j] -= 1
	rem[j][i] -= 1
	for x in range(4):
		l = []
		if been[x] == 0:
			dfs(x, l)
		ans = max(ans, sum(l))
	w[j] += p[1]
	rem[i][j] += 1
	rem[j][i] += 1
print(ans)


n = int(input())
score00 = [0] * 4
grid = []
for i in range(4):
	grid.append([])
	for j in range(4):
		grid[-1].append([])
for i in range(n):
	(a, x, b) = map(int, input().split())
	if a == b:
		score00[a - 1] += x
		continue
	if b < a:
		tmp = a
		a = b
		b = tmp
	grid[a - 1][b - 1].append(x)
for i in range(4):
	for j in range(4):
		grid[i][j].sort()
ans1 = 0
for i in range(2 ** 16):
	tmp = 0
	score = []
	fail = 0
	for j in range(4):
		score.append([0] * 4)
	degrees = [0] * 4
	for j in range(4):
		for k in range(j + 1, 4):
			if i & 1 << j * 4 + k:
				if not grid[j][k]:
					fail = 1
					break
				score[j][k] = sum(grid[j][k]) - grid[j][k][0]
				degrees[j] += len(grid[j][k]) - 1
				degrees[k] += len(grid[j][k]) - 1
			else:
				if grid[j][k]:
					score[j][k] = sum(grid[j][k])
				degrees[j] += len(grid[j][k])
				degrees[k] += len(grid[j][k])
		if fail:
			break
	if fail:
		continue
	count = 0
	for j in range(4):
		if degrees[j] % 2 == 1:
			count += 1
	if count == 4:
		continue
	totalscore = 0
	for j in range(4):
		for k in range(4):
			totalscore += score[j][k]
	if score[0][1] + score[2][3] == totalscore:
		if score[0][1] == 0:
			l = max(score00[0], score00[1])
		else:
			l = score[0][1] + score00[0] + score00[1]
		if score[2][3] == 0:
			r = max(score00[2], score00[3])
		else:
			r = score[2][3] + score00[2] + score00[3]
		ans = max(l, r)
	elif score[0][2] + score[1][3] == totalscore:
		if score[0][2] == 0:
			l = max(score00[0], score00[2])
		else:
			l = score[0][2] + score00[0] + score00[2]
		if score[1][3] == 0:
			r = max(score00[1], score00[3])
		else:
			r = score[1][3] + score00[1] + score00[3]
		ans = max(l, r)
	elif score[0][3] + score[1][2] == totalscore:
		if score[0][3] == 0:
			l = max(score00[0], score00[3])
		else:
			l = score[0][3] + score00[0] + score00[3]
		if score[1][2] == 0:
			r = max(score00[1], score00[2])
		else:
			r = score[1][2] + score00[1] + score00[2]
		ans = max(l, r)
	else:
		tmp = [0] * 4
		for j in range(4):
			for k in range(4):
				if score[j][k] != 0:
					tmp[j] = 1
					tmp[k] = 1
		ans = totalscore
		for j in range(4):
			if tmp[j]:
				ans += score00[j]
	ans1 = max(ans1, ans)
print(ans1)


class Domino:

	def __init__(self, side1, side2, value, double, parts):
		self.side1 = side1
		self.side2 = side2
		self.value = value
		self.double = double
		self.parts = parts

	def __repr__(self):
		return str(self.side1) + '-' + str(self.side2) + '-' + str(self.double) + '-' + str(self.value) + '-' + '|'.join([str(i) for i in self.parts])

	def __add__(self, other):
		if self.side1 == other.side2:
			return Domino(self.side2, other.side1, self.value + other.value, self.side2 == other.side1, self.parts + other.parts)
		elif self.side1 == other.side1:
			return Domino(self.side2, other.side2, self.value + other.value, self.side2 == other.side2, self.parts + other.parts)
		elif self.side2 == other.side2:
			return Domino(self.side1, other.side1, self.value + other.value, self.side1 == other.side1, self.parts + other.parts)
		elif self.side2 == other.side1:
			return Domino(self.side1, other.side2, self.value + other.value, self.side1 == other.side2, self.parts + other.parts)
		else:
			return Domino(0, 0, 0, True, [-1])

def SortByValue(Domino):
	return Domino.value

def SortByDup(Domino):
	return Domino.double

def addbycolor(self, other, color):
	if self.side1 == color and other.side2 == color:
		return Domino(self.side2, other.side1, self.value + other.value, self.side2 == other.side1, self.parts + other.parts)
	elif self.side1 == color and other.side1 == color:
		return Domino(self.side2, other.side2, self.value + other.value, self.side2 == other.side2, self.parts + other.parts)
	elif self.side2 == color and other.side2 == color:
		return Domino(self.side1, other.side1, self.value + other.value, self.side1 == other.side1, self.parts + other.parts)
	elif self.side2 == color and other.side1 == color:
		return Domino(self.side1, other.side2, self.value + other.value, self.side1 == other.side2, self.parts + other.parts)
	else:
		raise Exception

def delcolor(l, num):
	p = 1
	while p == 1:
		p = 0
		for i in range(len(l) - 1):
			for j in range(i + 1, len(l)):
				if (l[i].side1 == num or l[i].side2 == num) and (l[j].side1 == num or l[j].side2 == num):
					a = l.pop(i)
					b = l.pop(j - 1)
					ab = addbycolor(a, b, num)
					l.append(ab)
					p = 1
					l.sort(key=SortByValue)
					l.sort(key=SortByDup)
					l.reverse()
					break
			if p == 1:
				break
	l.sort(key=SortByValue)
	l.sort(key=SortByDup)
	l.reverse()
	return l

def getvalue(l):
	value = 0
	for i in l:
		value += i.value
n = int(input())
l = []
l_dup = []
for i in range(n):
	(q, w, e) = [int(el) for el in input().split()]
	if q == e + 100:
		l_dup.append(Domino(q, e, w, q == e, [i]))
	else:
		l.append(Domino(q, e, w, q == e, [i]))
l.sort(key=SortByValue)
l.sort(key=SortByDup)
l.reverse()
out = 0
s1 = [1, 2, 3, 4]
for i1 in s1:
	s2 = s1.copy()
	s2.remove(i1)
	for i2 in s2:
		s3 = s2.copy()
		s3.remove(i2)
		for i3 in s3:
			s4 = s3.copy()
			s4.remove(i3)
			for i4 in s4:
				l1 = l.copy()
				cc = len(l1)
				cont = 1
				while cont == 1:
					cont = 0
					l1 = delcolor(l1, i1)
					l1 = delcolor(l1, i2)
					l1 = delcolor(l1, i3)
					l1 = delcolor(l1, i4)
					if len(l1) < cc:
						cc = len(l1)
						cont = 1
				l1.sort(key=SortByValue)
				l1.reverse()
				out = max(out, l1[0].value)
print(out)


class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return
n = int(input())
d = [[] for _ in range(4)]
uf = UnionFind(4)
CVC = [list(map(int, input().split())) for _ in range(n)]
vals = []
min_not_auto = float('inf')
for i in range(n):
	cvc = CVC[i]
	vals.append(cvc[1])
	d[cvc[0] - 1].append(cvc[1])
	d[cvc[2] - 1].append(cvc[1])
	if cvc[0] != cvc[2] and cvc[1] < min_not_auto:
		min_not_auto = cvc[1]
	uf.union(cvc[0] - 1, cvc[2] - 1)
root_num = 0
for i in range(4):
	if uf.table[i] < 0:
		root_num += 1
if root_num == 1:
	odd = True
	for i in range(4):
		if len(d[i]) % 2 == 0:
			odd = False
			break
	if odd:
		print(sum(vals) - min_not_auto)
	else:
		answers = [0] * 4
		for i in range(4):
			answers[uf.find(i)] += sum(d[i])
		print(max(answers) // 2)
else:
	answers = [0] * 4
	for i in range(4):
		answers[uf.find(i)] += sum(d[i])
	print(max(answers) // 2)


from random import randint
values = [[] for _ in range(10)]
types = [[0, 1, 2, 3], [1, 4, 5, 6], [2, 5, 7, 8], [3, 6, 8, 9]]
b = [1] * 10
B = 128
for i in range(9):
	b[i + 1] = b[i] * B
for i in range(4):
	values[types[i][i]].append(0)
n = int(input())
for _ in range(n):
	(i, v, j) = map(int, input().split())
	t = types[i - 1][j - 1]
	if i == j:
		values[t][0] += v
	else:
		values[t].append(v)
for i in range(4):
	for j in range(i + 1, 4):
		t = types[i][j]
		values[t].sort()
		while len(values[t]) > 3:
			v = values[t].pop() + values[t].pop()
			values[t][-1] += v
		values[t].sort(reverse=True)
cur = [{}, {}, {}, {}]
m = 0
for i in range(4):
	for j in range(i, 4):
		t = types[i][j]
		if values[t]:
			cur[i][b[t]] = values[t][0]
			m = max(m, values[t][0])

def cnt(k, t):
	return k // b[t] % B
for _ in range(n):
	next = [{}, {}, {}, {}]
	for i in range(4):
		for j in range(4):
			t = types[i][j]
			for (k, v) in cur[i].items():
				c = cnt(k, t)
				if len(values[t]) > c:
					nk = k + b[t]
					if nk not in next[j]:
						next[j][nk] = values[t][c] + v
						m = max(m, values[t][c] + v)
	cur = next
print(m)