AtCoder Beginner Contest 176 - Brave CHAIN

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

* Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.



After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_{3N}


Output

Print the maximum number of points you can gain.

Examples

Input

2
1 2 1 2 2 1


Output

2


Input

3
1 1 2 2 3 3 3 2 1


Output

1


Input

3
1 1 2 2 2 3 3 3 1


Output

3

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10 ** 10] * (N + 1) for _ in range(N + 1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-5] * (N + 1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
	B = A[i * 3 + 2:i * 3 + 5]
	cnt = len(set(B))
	if cnt == 1:
		ans += 1
	elif cnt == 2:
		a1 = B[0] ^ B[1] ^ B[2]
		a2 = (sum(B) - a1) // 2
		(X[a1], X[a1][a2], X[a2][a2]) = ([max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N + 1)], max(ma, X[a2][a2] + 1), max(ma, X[a1][a1] + 1))
		X[a2] = [max(x, m) for (x, m) in zip(X[a2], MA)]
		MA = [max(m, x1, x2) for (m, x1, x2) in zip(MA, X[a1], X[a2])]
		MA[a1] = max(MA[a1], max(X[a1]))
		MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
		ma = max(ma, MA[a1], MA[a2])
	else:
		(a, b, c) = B
		(X[a][b], X[a][c], X[b][c]) = (max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1))
		X[a] = [max(x, m) for (x, m) in zip(X[a], MA)]
		X[b] = [max(x, m) for (x, m) in zip(X[b], MA)]
		X[c] = [max(x, m) for (x, m) in zip(X[c], MA)]
		MA[a] = max(MA[a], max(X[a]))
		MA[b] = max(MA[b], X[a][b], max(X[b]))
		MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
		MA = [max(m, xa, xb, xc) for (m, xa, xb, xc) in zip(MA, X[a], X[b], X[c])]
		ma = max(ma, MA[a], MA[b], MA[c])
print(ans + max(ma, max((max(x) for x in X))))


import sys
input = sys.stdin.readline
N = int(input().strip()) + 2
A = list(map(int, input().split())) + [N - 1, N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
(a, b, c, d, e) = [i - 1 for i in sorted(A[:5])]
if a == b == c:
	dp[d][e] = dp[e][d] = dpmaxj[d] = dpmaxj[e] = dpmax = 1
elif b == c == d:
	dp[a][e] = dp[e][a] = dpmaxj[a] = dpmaxj[e] = dpmax = 1
elif c == d == e:
	dp[a][b] = dp[b][a] = dpmaxj[a] = dpmaxj[b] = dpmax = 1
else:
	L = [a, b, c, d, e]
	for i in range(5):
		for j in range(i + 1, 5):
			(p, q) = (L[i], L[j])
			dp[p][q] = dp[q][p] = dpmaxj[p] = dpmaxj[q] = 0
	dpmax = 0

def update(i, j):
	dpmaxj[i] = max(dpmaxj[i], dp[i][j])
	dpmaxj[j] = max(dpmaxj[j], dp[i][j])
for i in range(N - 3):
	prevdpmax = dpmax
	prevdpmaxj = dpmaxj[:]
	dpd = [dp[k][k] for k in range(N)]
	(a, b, c) = A[i * 3 + 5:i * 3 + 8]
	a -= 1
	b -= 1
	c -= 1
	prevdpka = [dp[i][a] for i in range(N)]
	prevdpla = [dp[a][i] for i in range(N)]
	prevdpkb = [dp[i][b] for i in range(N)]
	prevdplb = [dp[b][i] for i in range(N)]
	if a == b == c:
		score += 1
		continue
	elif a == b:
		for k in range(N):
			dp[k][c] = max(dp[k][c], max(prevdpka[k], prevdpla[k]) + 1)
			dp[c][k] = max(dp[c][k], max(prevdpka[k], prevdpla[k]) + 1)
			dpmax = max(dpmax, dp[k][c], dp[c][k])
			update(k, c)
			update(c, k)
	elif a == c:
		for k in range(N):
			dp[k][b] = max(dp[k][b], max(prevdpka[k], prevdpla[k]) + 1)
			dp[b][k] = max(dp[b][k], max(prevdpka[k], prevdpla[k]) + 1)
			dpmax = max(dpmax, dp[k][b], dp[b][k])
			update(k, b)
			update(b, k)
	elif b == c:
		for k in range(N):
			dp[k][a] = max(dp[k][a], max(prevdpkb[k], prevdplb[k]) + 1)
			dp[a][k] = max(dp[a][k], max(prevdpkb[k], prevdplb[k]) + 1)
			dpmax = max(dpmax, dp[k][a], dp[a][k])
			update(k, a)
			update(a, k)
	dp[b][c] = max(dp[b][c], dpd[a] + 1)
	dp[c][b] = max(dp[c][b], dpd[a] + 1)
	dp[a][c] = max(dp[a][c], dpd[b] + 1)
	dp[c][a] = max(dp[c][a], dpd[b] + 1)
	dp[a][b] = max(dp[a][b], dpd[c] + 1)
	dp[b][a] = max(dp[b][a], dpd[c] + 1)
	dpmax = max(dpmax, dp[b][c], dp[a][c], dp[a][b], dp[c][b], dp[c][a], dp[b][a])
	dp[a][b] = max(0, dp[a][b], prevdpmax)
	dp[b][a] = max(0, dp[b][a], prevdpmax)
	dp[b][c] = max(0, dp[b][c], prevdpmax)
	dp[c][b] = max(0, dp[c][b], prevdpmax)
	dp[a][c] = max(0, dp[a][c], prevdpmax)
	dp[c][a] = max(0, dp[c][a], prevdpmax)
	update(a, b)
	update(a, c)
	update(b, a)
	update(b, c)
	update(c, a)
	update(c, b)
	for j in range(N):
		dp[j][a] = max(dp[j][a], prevdpmaxj[j])
		dp[j][b] = max(dp[j][b], prevdpmaxj[j])
		dp[j][c] = max(dp[j][c], prevdpmaxj[j])
		dp[a][j] = max(dp[a][j], prevdpmaxj[j])
		dp[b][j] = max(dp[b][j], prevdpmaxj[j])
		dp[c][j] = max(dp[c][j], prevdpmaxj[j])
		update(j, a)
		update(j, b)
		update(j, c)
		update(a, j)
		update(b, j)
		update(c, j)
print(max(dp[N - 2][N - 1], dp[N - 1][N - 2]) + score)


def solve(n, aaa):
	dp = [[-1] * n for _ in range(n)]
	dp_max = [-1] * n
	ans = 0
	(a0, a1) = sorted(aaa[:2])
	dp[a0][a1] = 0
	dp_max[a0] = 0
	dp_max[a1] = 0
	for k in range(n - 1):
		(a0, a1, a2) = sorted(aaa[2 + 3 * k:5 + 3 * k])
		if a0 == a1 and a1 == a2:
			ans += 1
			continue
		dp_max_max = max(dp_max)
		update_tasks = []
		if a0 == a1 or a1 == a2:
			rev = a1 == a2
			if rev:
				(a0, a2) = (a2, a0)
			for b in range(n):
				(c, d) = (min(a0, b), max(a0, b))
				(e, f) = (min(a2, b), max(a2, b))
				update_tasks.append((e, f, dp_max[b]))
				if dp[c][d] != -1:
					update_tasks.append((e, f, dp[c][d] + 1))
			update_tasks.append((a0, a0, dp_max_max))
			if dp[a2][a2] != -1:
				update_tasks.append((a0, a0, dp[a2][a2] + 1))
			if rev:
				update_tasks.append((a2, a0, dp_max_max))
			else:
				update_tasks.append((a0, a2, dp_max_max))
		else:
			update_tasks.append((a0, a1, dp_max_max))
			update_tasks.append((a0, a2, dp_max_max))
			update_tasks.append((a1, a2, dp_max_max))
			if dp[a0][a0] != -1:
				update_tasks.append((a1, a2, dp[a0][a0] + 1))
			if dp[a1][a1] != -1:
				update_tasks.append((a0, a2, dp[a1][a1] + 1))
			if dp[a2][a2] != -1:
				update_tasks.append((a0, a1, dp[a2][a2] + 1))
			for b in range(n):
				b_max = dp_max[b]
				for a in (a0, a1, a2):
					(c, d) = (min(a, b), max(a, b))
					update_tasks.append((c, d, b_max))
		for (a, b, c) in update_tasks:
			dp[a][b] = max(dp[a][b], c)
			dp_max[a] = max(dp_max[a], c)
			dp_max[b] = max(dp_max[b], c)
	a = aaa[-1]
	dp[a][a] += 1
	return max(map(max, dp)) + ans
n = int(input())
aaa = [a - 1 for a in map(int, input().split())]
ans = solve(n, aaa)
print(ans)


def insertR(a, b):
	if a not in R:
		R[a] = {}
	if b not in R[a]:
		R[a][b] = 0
N = int(input())
A = list(map(int, input().split()))
if N == 1:
	print(1)
	exit()
DP = [[-1] * (N + 1) for _ in range(N + 1)]
D = [-1] * (N + 1)
R = {}
for i in range(5):
	a = A[i]
	if a in R:
		R[a] += 1
	else:
		R[a] = 1
Flag = 0
for i in R.keys():
	if R[i] >= 3:
		Flag = 1
		R[i] -= 3
L = []
for i in R.keys():
	if R[i] == 2:
		L.append(i)
		DP[i][i] = Flag
		D[i] = Flag
	elif R[i] == 1:
		L.append(i)
		D[i] = Flag
for i in range(len(L) - 1):
	for j in range(i + 1, len(L)):
		DP[L[i]][L[j]] = Flag
common = 0
for i in range(5, N * 3 - 3, 3):
	L = []
	for j in range(i, i + 3):
		for k in range(len(L)):
			if L[k][1] == A[j]:
				L[k][0] += 1
				break
		else:
			L.append([1, A[j]])
	L.sort()
	R = {}
	if len(L) == 1:
		common += 1
	elif len(L) == 2:
		a = L[0][1]
		b = L[1][1]
		if DP[a][a] != -1:
			insertR(b, b)
			R[b][b] = max([R[b][b], DP[b][b], DP[a][a] + 1])
		for j in range(N + 1):
			n = max(DP[b][j], DP[j][b])
			if n == -1:
				continue
			insertR(a, j)
			R[a][j] = max([R[a][j], DP[a][j], n + 1])
		for j in range(N + 1):
			n = D[j]
			if n == -1:
				continue
			insertR(a, j)
			R[a][j] = max(R[a][j], n)
			insertR(b, j)
			R[b][j] = max(R[b][j], n)
		n = max(D)
		insertR(a, b)
		R[a][b] = max(R[a][b], n)
		insertR(b, b)
		R[b][b] = max(R[b][b], n)
	elif len(L) == 3:
		a = L[0][1]
		b = L[1][1]
		c = L[2][1]
		insertR(b, c)
		insertR(a, c)
		insertR(a, b)
		if DP[a][a] != -1:
			R[b][c] = max(R[b][c], DP[a][a] + 1)
		if DP[b][b] != -1:
			R[a][c] = max(R[a][c], DP[b][b] + 1)
		if DP[c][c] != -1:
			R[a][b] = max(R[a][b], DP[c][c] + 1)
		for j in range(N + 1):
			n = D[j]
			if n == -1:
				continue
			insertR(a, j)
			R[a][j] = max(R[a][j], n)
			insertR(b, j)
			R[b][j] = max(R[b][j], n)
			insertR(c, j)
			R[c][j] = max(R[c][j], n)
		n = max(D)
		R[a][b] = max(R[a][b], n)
		R[b][c] = max(R[b][c], n)
		R[a][c] = max(R[a][c], n)
	for k in R.keys():
		for kk in R[k].keys():
			n = R[k][kk]
			DP[k][kk] = max(DP[k][kk], n)
			DP[kk][k] = max(DP[kk][k], n)
			D[k] = max(D[k], n)
			D[kk] = max(D[kk], n)
a = A[-1]
if DP[a][a] != -1:
	DP[a][a] += 1
ans = 0
for i in DP:
	for j in i:
		ans = max(ans, j)
ans += common
print(ans)


N = int(input())
A = list(map(int, input().split()))
INF = 2 * N
DP = [[-INF] * (N + 1) for _ in range(N + 1)]
M = 0
rowM = [-INF] * (N + 1)

def chmax(i, j, k):
	DP[i][j] = max(k, DP[i][j])
	DP[j][i] = max(k, DP[j][i])
	rowM[i] = max(rowM[i], DP[i][j])
	rowM[j] = max(rowM[j], DP[i][j])
	global M
	M = max(M, k)
ans = 0
DP[A[0]][A[1]] = 0
DP[A[1]][A[0]] = 0
rowM[A[0]] = 0
rowM[A[1]] = 0
for i in range(N - 1):
	new = A[3 * i + 2:3 * i + 5]
	change = []
	if len(set(new)) == 1:
		ans += 1
		continue
	if len(set(new)) == 2:
		for j in range(3):
			if new.count(new[j]) == 2:
				X = new[j]
			else:
				Y = new[j]
		for j in range(1, N + 1):
			change.append((j, Y, DP[X][j] + 1))
	(X, Y, Z) = new
	change.append((X, Y, DP[Z][Z] + 1))
	change.append((Y, Z, DP[X][X] + 1))
	change.append((X, Z, DP[Y][Y] + 1))
	change.append((X, Y, M))
	change.append((X, Z, M))
	change.append((Y, Z, M))
	for j in range(1, N + 1):
		for k in range(3):
			change.append((j, new[k], rowM[j]))
	for (j, k, l) in change:
		chmax(j, k, l)
M = max(M, DP[A[-1]][A[-1]] + 1)
print(ans + M)


from collections import deque

def upd(a, b, v):
	global N
	dp[a][b] = max(dp[a][b], v)
	dp[b][a] = max(dp[b][a], v)
	dp[N][a] = max(dp[N][a], v)
	dp[N][b] = max(dp[N][b], v)
	dp[a][N] = max(dp[a][N], v)
	dp[b][N] = max(dp[b][N], v)
	dp[N][N] = max(dp[N][N], v)
N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))
INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0
for i in range(2, 3 * N - 1, 3):
	(x, y, z) = (A[i], A[i + 1], A[i + 2])
	if x == y == z:
		base += 1
	else:
		q = deque()
		for _ in range(3):
			for k in range(N):
				v = dp[k][N]
				if y == z:
					v = max(v, dp[k][y] + 1)
				q.append((k, x, v))
			v = max(dp[z][z] + 1, dp[N][N])
			q.append((x, y, v))
			(x, y, z) = (z, x, y)
		while q:
			(a, b, v) = q.popleft()
			upd(a, b, v)
l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-10] * (n + 1)
nmx = [-10] * (n + 1)
(a, b) = (min(aa[:2]), max(aa[:2]))
dp[a][b] = dp[b][a] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
	if val < 0:
		return
	if val > dp[i][j]:
		dp[i][j] = dp[j][i] = val
		nmx[i] = max(nmx[i], val)
		nmx[j] = max(nmx[j], val)
		nmx[n] = max(nmx[n], val)
base = 0
for i in range(n - 1):
	abc = aa[i * 3 + 2:i * 3 + 5]
	abc.sort()
	(a, b, c) = abc
	if a == c:
		base += 1
		continue
	if b == c:
		(a, c) = (c, a)
	if a == b:
		vc = dp[c][c]
		for (x, v) in enumerate(dp[a][:]):
			chmax(c, x, v + 1)
		chmax(a, c, max(mx[n], dp[a][a] + 1))
		chmax(a, a, max(mx[n], vc + 1))
		for x in range(n):
			chmax(a, x, mx[x])
		for x in range(n):
			chmax(c, x, mx[x])
	else:
		chmax(b, c, max(dp[a][a] + 1, mx[n]))
		chmax(a, c, max(dp[b][b] + 1, mx[n]))
		chmax(a, b, max(dp[c][c] + 1, mx[n]))
		for x in range(n):
			chmax(a, x, mx[x])
			chmax(b, x, mx[x])
			chmax(c, x, mx[x])
	for x in range(n + 1):
		mx[x] = max(mx[x], nmx[x])
a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)


n = int(input())
A = list(map(int, input().split()))
dp = [[-float('INF')] * (n + 1) for i in range(n + 1)]
low = [-float('INF')] * (n + 1)
m = 0
(a, b) = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0
for _ in range(1, n):
	(a, b, c) = A[3 * _ - 1:3 * _ + 2]
	q = []
	if a == b == c:
		base += 1
		continue
	m1 = m
	for j in range(3):
		q.append((a, b, max(m, dp[c][c] + 1)))
		m1 = max(m1, dp[c][c] + 1)
		for i in range(1, n + 1):
			q.append((a, i, low[i]))
		if a == b:
			for i in range(1, n + 1):
				q.append((c, i, dp[a][i] + 1))
				m1 = max(m1, dp[a][i] + 1)
		(a, b, c) = (b, c, a)
	for (a, b, v) in q:
		dp[a][b] = max(dp[a][b], v)
		dp[b][a] = max(dp[b][a], v)
		low[a] = max(low[a], v)
		low[b] = max(low[b], v)
	m = m1
print(max(m, dp[A[-1]][A[-1]] + 1) + base)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = list(map(int, input().split()))
	ans = [[-N] * (N + 1) for _ in range(N + 1)]
	(a0, a1) = A[:2]
	ans[a0][a1] = 0
	ans[a1][a0] = 0
	ma = [-N] * (N + 1)
	ma[a0] = 0
	ma[a1] = 0
	mama = 0
	add = 0
	for i in range(N - 1):
		(a, b, c) = A[i * 3 + 2:i * 3 + 5]
		if a == b == c:
			add += 1
			continue
		Q = []
		for _ in range(3):
			(a, b, c) = (b, c, a)
			Q.append((a, b, max(mama, ans[c][c] + 1)))
			for j in range(1, N + 1):
				val = ma[j]
				if b == c:
					val = max(val, ans[b][j] + 1)
				Q.append((a, j, val))
		for (i, j, val) in Q:
			ans[i][j] = max(ans[i][j], val)
			ans[j][i] = max(ans[j][i], val)
			ma[i] = max(ma[i], val)
			ma[j] = max(ma[j], val)
			mama = max(mama, val)
	ANS = 0
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if i == j == A[-1]:
				ANS = max(ANS, ans[i][j] + 1)
			else:
				ANS = max(ANS, ans[i][j])
	print(ANS + add)
main()


N = int(input())
A = list(map(int, input().split()))
if N == 1:
	if A[0] == A[1] == A[2]:
		print(1)
	else:
		print(0)
	exit()
INF = float('inf')
ans = 0
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]
use = {A[0], A[1]}
for i in range(N - 1):
	(a, b, c) = A[i * 3 + 2:i * 3 + 5]
	if a == b == c:
		ans += 1
		continue
	update = []
	if a == b:
		for j in use:
			update.append((j, c, max(dp[a][j], dp[j][a]) + 1))
	elif b == c:
		for j in use:
			update.append((j, a, max(dp[b][j], dp[j][b]) + 1))
	elif c == a:
		for j in use:
			update.append((j, b, max(dp[c][j], dp[j][c]) + 1))
	update.append((a, b, dp[c][c] + 1))
	update.append((b, c, dp[a][a] + 1))
	update.append((c, a, dp[b][b] + 1))
	mx = max(maxdp)
	update.append((a, b, mx))
	update.append((b, c, mx))
	update.append((c, a, mx))
	for j in use:
		update.append((j, a, maxdp[j]))
		update.append((j, b, maxdp[j]))
		update.append((j, c, maxdp[j]))
	for (l, m, n) in update:
		dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
		maxdp[l] = max(maxdp[l], n)
		maxdp[m] = max(maxdp[m], n)
	use.add(a)
	use.add(b)
	use.add(c)
tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)


N = int(input())
A = list(map(int, input().split()))
N = len(A) // 3
A = A[:3 * N]
A.append(0)
A.append(0)
ans = 0

def ind(a, b):
	t = sorted((a, b))
	return t[0] * (N + 1) + t[1]

def inv(i):
	b = i % (N + 1)
	a = i // (N + 1)
	return (a, b)
dp = [-1] * (N + 1) ** 2
dp[ind(A[0], A[1])] = 0
current_max = 0
dp1 = [-1] * (N + 1)
dp1[A[0]] = 0
dp1[A[1]] = 0
ans = 0
for i in range(0, N):
	a = A[2 + 3 * i]
	b = A[2 + 3 * i + 1]
	c = A[2 + 3 * i + 2]
	if a == b == c:
		ans += 1
		continue
	dp_new = {}
	for (x, y, z) in [(a, b, c), (b, c, a), (c, a, b)]:
		i = ind(y, z)
		if i not in dp_new:
			dp_new[i] = 0
		dp_new[i] = max(dp_new[i], current_max)
		if dp[ind(x, x)] >= 0:
			dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
		for t in range(1, N + 1):
			i = ind(t, z)
			if dp1[t] >= 0:
				if i not in dp_new:
					dp_new[i] = 0
				dp_new[i] = max(dp_new[i], dp1[t])
			if x == y and dp[ind(t, x)] >= 0:
				if i not in dp_new:
					dp_new[i] = 0
				dp_new[i] = max(dp_new[i], dp[ind(t, x)] + 1)
	for (i, s) in dp_new.items():
		dp[i] = max(dp[i], s)
		(ta, tb) = inv(i)
		dp1[ta] = max(dp1[ta], s)
		dp1[tb] = max(dp1[tb], s)
		current_max = max(current_max, s)
print(ans + max(dp1))


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
INF = 1 << 50

def run():
	(N, *A_) = map(int, read().split())
	dp = [[-INF] * (N + 1) for _ in range(N + 1)]
	dp_max = [-INF] * (N + 1)
	(a, b) = A_[:2]
	dp[a][b] = dp[b][a] = dp_max[a] = dp_max[b] = 0
	triplets = 0
	chunks = []
	for i in range(N - 1):
		(x, y, z) = A_[3 * i + 2:3 * i + 5]
		if x == y == z:
			triplets += 1
		else:
			chunks.append((x, y, z))
	for (x, y, z) in chunks:
		cache = []
		if y == z:
			(x, y, z) = (y, z, x)
		elif z == x:
			(x, y, z) = (z, x, y)
		if x == y:
			for i in range(1, N + 1):
				cache.append((z, i, dp[x][i] + 1))
		cache.append((y, z, dp[x][x] + 1))
		cache.append((z, x, dp[y][y] + 1))
		cache.append((x, y, dp[z][z] + 1))
		MAX = max(dp_max)
		cache.append((x, y, MAX))
		cache.append((y, z, MAX))
		cache.append((z, x, MAX))
		for i in range(1, N + 1):
			cache.append((i, x, dp_max[i]))
			cache.append((i, y, dp_max[i]))
			cache.append((i, z, dp_max[i]))
		for (a, b, value) in cache:
			dp[a][b] = dp[b][a] = max(value, dp[a][b])
			dp_max[a] = max(dp_max[a], dp[a][b])
			dp_max[b] = max(dp_max[b], dp[a][b])
	a = A_[-1]
	dp[a][a] += 1
	dp_max[a] = max(dp[a][a], dp_max[a])
	print(max(dp_max) + triplets)
run()


N = int(input())
A = list(map(int, input().split()))
ans = [[-N] * (N + 1) for _ in range(N + 1)]
(a0, a1) = A[:2]
ans[a0][a1] = 0
ans[a1][a0] = 0
ma = [-N] * (N + 1)
ma[a0] = 0
ma[a1] = 0
all_max = 0
add = 0
for i in range(N - 1):
	(a, b, c) = (A[3 * i + 2], A[3 * i + 3], A[3 * i + 4])
	if a == b == c:
		add += 1
		continue
	Q = []
	for _ in range(3):
		(a, b, c) = (b, c, a)
		Q.append((a, b, max(all_max, ans[c][c] + 1)))
		for j in range(1, N + 1):
			val = ma[j]
			if b == c:
				val = max(val, ans[b][j] + 1)
			Q.append((a, j, val))
	for (i, j, val) in Q:
		ans[i][j] = max(ans[i][j], val)
		ans[j][i] = max(ans[j][i], val)
		ma[i] = max(ma[i], val)
		ma[j] = max(ma[j], val)
		all_max = max(all_max, val)
answer = 0
for i in range(1, N + 1):
	for j in range(1, N + 1):
		if i == j == A[-1]:
			answer = max(answer, ans[i][j] + 1)
		else:
			answer = max(answer, ans[i][j])
print(answer + add)


import sys
sys.setrecursionlimit(500005)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
n = ni()
a = na()
dp = [[-99999999] * (n + 1) for _ in range(n + 1)]
dp[a[0]][a[1]] = 0
dprow = [-99999999] * (n + 1)
dprow[a[0]] = 0
dprow[a[1]] = 0
margin = 0
for i in range(2, 3 * n - 2, 3):
	if a[i] == a[i + 1] and a[i + 1] == a[i + 2]:
		margin += 1
	else:
		q = []
		for jj in range(i, i + 3):
			if dp[a[jj]][a[jj]] < 0:
				continue
			if jj == i:
				q.append((a[i + 1], a[i + 2], dp[a[jj]][a[jj]] + 1))
			if jj == i + 1:
				q.append((a[i], a[i + 2], dp[a[jj]][a[jj]] + 1))
			if jj == i + 2:
				q.append((a[i], a[i + 1], dp[a[jj]][a[jj]] + 1))
		for jj in range(i, i + 3):
			for kk in range(jj + 1, i + 3):
				if a[jj] == a[kk]:
					rem = i + i + 1 + i + 2 - jj - kk
					for t in range(n + 1):
						if dp[a[jj]][t] >= 0:
							q.append((t, a[rem], dp[a[jj]][t] + 1))
						if dp[t][a[jj]] >= 0:
							q.append((t, a[rem], dp[t][a[jj]] + 1))
		for j in range(n + 1):
			if dprow[j] >= 0:
				for k in (a[i], a[i + 1], a[i + 2]):
					q.append((j, k, dprow[j]))
		mx = max(dprow)
		for jj in range(i, i + 3):
			for kk in range(jj + 1, i + 3):
				q.append((a[jj], a[kk], mx))
		for u in q:
			dp[u[0]][u[1]] = max(dp[u[0]][u[1]], u[2])
			dprow[u[0]] = max(dprow[u[0]], u[2])
			dprow[u[1]] = max(dprow[u[1]], u[2])
ans = max(*dprow, dp[a[-1]][a[-1]] + 1)
print(ans + margin)


n = int(input())
a = [*map(int, input().split())]
for i in range(n * 3):
	a[i] -= 1
INF = 1 << 30
dp = [[-INF] * n for i in range(n)]
mx = [-INF] * n
mx_all = -INF
add_all = 0
dp[a[0]][a[1]] = dp[a[1]][a[0]] = 0
mx[a[0]] = mx[a[1]] = 0
mx_all = 0
for i in range(n - 1):
	(x, y, z) = sorted(a[i * 3 + 2:i * 3 + 5])
	update = []
	if x == y == z:
		add_all += 1
		continue
	if x == y:
		for j in range(n):
			update.append((j, z, dp[j][x] + 1))
	if y == z:
		for j in range(n):
			update.append((j, x, dp[j][y] + 1))
	update.append((y, z, dp[x][x] + 1))
	update.append((x, z, dp[y][y] + 1))
	update.append((x, y, dp[z][z] + 1))
	for j in range(n):
		update.append((j, x, mx[j]))
		update.append((j, y, mx[j]))
		update.append((j, z, mx[j]))
	update.append((y, z, mx_all))
	update.append((x, z, mx_all))
	update.append((x, y, mx_all))
	for (j, k, val) in update:
		if dp[j][k] < val:
			dp[j][k] = dp[k][j] = val
		if mx[j] < val:
			mx[j] = val
		if mx[k] < val:
			mx[k] = val
		if mx_all < val:
			mx_all = val
if mx_all < dp[a[-1]][a[-1]] + 1:
	mx_all = dp[a[-1]][a[-1]] + 1
print(mx_all + add_all)


import math
import itertools
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
alp = 'abcdefghijklmnopqrstuvwxyz'

def main():
	n = int(ipt())
	a = [int(i) - 1 for i in ipt().split()]
	dp = [[-10000] * n for i in range(n)]
	add = 0
	ma = 0
	manm = [-10000] * n
	manm[a[0]] = 0
	manm[a[1]] = 0
	dp[a[0]][a[1]] = 0
	for k in range(3, 3 * n, 3):
		a0 = a[k - 1]
		a1 = a[k]
		a2 = a[k + 1]
		if a0 == a1 == a2:
			add += 1
		elif a0 != a1 != a2 != a0:
			pdp0 = dp[a0][a0] * 1
			pdp1 = dp[a1][a1] * 1
			pdp2 = dp[a2][a2] * 1
			dp0 = dp[a0]
			dp1 = dp[a1]
			dp2 = dp[a2]
			for i in range(n):
				dp0[i] = manm[i]
				dp1[i] = manm[i]
				dp2[i] = manm[i]
			if ma < pdp0 + 1:
				dp1[a2] = pdp0 + 1
			else:
				dp1[a2] = ma
			if ma < pdp1 + 1:
				dp0[a2] = pdp1 + 1
			else:
				dp0[a2] = ma
			if ma < pdp2 + 1:
				dp0[a1] = pdp2 + 1
			else:
				dp0[a1] = ma
			manm[a0] = max(dp0)
			manm[a1] = max(dp1)
			manm[a2] = max(dp2)
			if manm[a2] < dp1[a2]:
				manm[a2] = dp1[a2]
			if manm[a2] < dp0[a2]:
				manm[a2] = dp0[a2]
			if manm[a1] < dp0[a1]:
				manm[a1] = dp0[a1]
			ma = max(manm)
		else:
			if a0 == a1:
				p = a0
				q = a2
			elif a1 == a2:
				p = a1
				q = a0
			else:
				p = a2
				q = a1
			pdpp = dp[p][p] * 1
			pdpq = dp[q][q] * 1
			dpp = dp[p]
			dpq = dp[q]
			do = []
			dpip = [dp[i][p] for i in range(n)]
			for i in range(n):
				if manm[i] >= dpp[i] + 1 and manm[i] >= dpip[i] + 1:
					dpq[i] = manm[i]
				elif dpp[i] > dpip[i]:
					dpq[i] = dpp[i] + 1
				else:
					dpq[i] = dpip[i] + 1
				do.append((q, dpq[i]))
				do.append((i, dpq[i]))
			for i in range(n):
				if manm[i] > dpp[i]:
					dpp[i] = manm[i]
					do.append((p, manm[i]))
			if ma > pdpq + 1:
				dpp[p] = ma
			else:
				dpp[p] = pdpq + 1
			do.append((p, dpp[p]))
			if ma > pdpp + 1:
				dpp[q] = ma
			else:
				dpp[q] = pdpp + 1
			do.append((p, dpp[q]))
			do.append((q, dpp[q]))
			for (i, j) in do:
				if manm[i] < j:
					manm[i] = j
			ma = max(manm)
	dp[a[-1]][a[-1]] += 1
	ma = 0
	for i in dp:
		for j in i:
			if j > ma:
				ma = j
	print(ma + add)
	return None
main()


N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10 ** 10] * (N + 1) for _ in range(N + 1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-10 ** 10] * (N + 1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
	B = A[i * 3 + 2:i * 3 + 5]
	cnt = len(set(B))
	if cnt == 1:
		ans += 1
	elif cnt == 2:
		a1 = B[0] ^ B[1] ^ B[2]
		a2 = (sum(B) - a1) // 2
		(X[a1], X[a1][a2], X[a2][a2]) = ([max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N + 1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1))
		X[a2] = [max(X[a2][j], MA[j]) for j in range(N + 1)]
		MA = [max(MA[j], X[a1][j], X[a2][j]) for j in range(N + 1)]
		MA[a1] = max(MA[a1], max(X[a1]), X[a2][a1])
		MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
		ma = max(ma, MA[a1], MA[a2])
	else:
		(a, b, c) = B
		(X[a][b], X[a][c], X[b][c]) = (max(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1))
		X[a] = [max(X[a][j], MA[j]) for j in range(N + 1)]
		X[b] = [max(X[b][j], MA[j]) for j in range(N + 1)]
		X[c] = [max(X[c][j], MA[j]) for j in range(N + 1)]
		MA[a] = max(MA[a], max(X[a]))
		MA[b] = max(MA[b], X[a][b], max(X[b]))
		MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
		MA = [max(MA[j], X[a][j], X[b][j], X[c][j]) for j in range(N + 1)]
		ma = max(ma, MA[a], MA[b], MA[c])
print(ans + max(ma, max((max(x) for x in X))))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
ANS = 0
B = [A[0], A[1]]
C = []
D = A[-1]
for i in range(N - 1):
	if A[i * 3 + 2] == A[i * 3 + 3] == A[i * 3 + 4]:
		ANS += 1
	else:
		C.append((A[i * 3 + 2], A[i * 3 + 3], A[i * 3 + 4]))
DP = [[-1] * (N + 1) for i in range(N + 1)]
MAXDP = [-1] * (N + 1)
SCMAX = 0
DP[B[0]][B[1]] = DP[B[1]][B[0]] = 0
MAXDP[B[0]] = 0
MAXDP[B[1]] = 0
for (x, y, z) in C:
	NLIST = []
	SCMAX2 = 0
	NMAXDP = [i for i in MAXDP]
	xy = max(0, DP[x][y], DP[z][z] + 1)
	yz = max(0, DP[y][z], DP[x][x] + 1)
	zx = max(0, DP[z][x], DP[y][y] + 1)
	if x == y:
		for i in range(N + 1):
			if DP[i][x] != -1:
				NLIST.append((i, z, max(DP[i][z], DP[i][x] + 1)))
			NMAXDP[i] = max(NMAXDP[i], DP[i][z], DP[z][i])
			NMAXDP[z] = max(NMAXDP[z], DP[i][z], DP[z][i])
	if y == z:
		for i in range(N + 1):
			if DP[i][y] != -1:
				NLIST.append((i, x, max(DP[i][x], DP[i][y] + 1)))
			NMAXDP[i] = max(NMAXDP[i], DP[i][x], DP[x][i])
			NMAXDP[x] = max(NMAXDP[x], DP[i][x], DP[x][i])
	if z == x:
		for i in range(N + 1):
			if DP[i][x] != -1:
				NLIST.append((i, y, max(DP[i][y], DP[i][x] + 1)))
			NMAXDP[i] = max(NMAXDP[i], DP[i][y], DP[y][i])
			NMAXDP[y] = max(NMAXDP[y], DP[i][y], DP[y][i])
	for (i, j, sc) in NLIST:
		DP[i][j] = DP[j][i] = max(DP[i][j], sc)
		SCMAX2 = max(SCMAX, DP[i][j])
	for i in range(N + 1):
		DP[i][x] = DP[x][i] = max(DP[i][x], MAXDP[i])
		DP[i][y] = DP[y][i] = max(DP[i][y], MAXDP[i])
		DP[i][z] = DP[z][i] = max(DP[i][z], MAXDP[i])
		SCMAX2 = max(SCMAX2, DP[i][x], DP[i][y], DP[i][z])
		NMAXDP[i] = max(NMAXDP[i], DP[i][x], DP[i][y], DP[i][z])
		NMAXDP[x] = max(NMAXDP[x], DP[i][x])
		NMAXDP[y] = max(NMAXDP[y], DP[i][y])
		NMAXDP[z] = max(NMAXDP[z], DP[i][z])
	DP[x][y] = DP[y][x] = max(SCMAX, xy)
	DP[y][z] = DP[z][y] = max(SCMAX, yz)
	DP[z][x] = DP[x][z] = max(SCMAX, zx)
	SCMAX2 = max(SCMAX2, DP[x][y], DP[y][z], DP[z][x])
	MAXDP = NMAXDP
	MAXDP[x] = max(MAXDP[x], DP[x][y], DP[y][x], DP[z][x], DP[x][z])
	MAXDP[y] = max(MAXDP[y], DP[x][y], DP[y][x], DP[z][y], DP[y][z])
	MAXDP[z] = max(MAXDP[z], DP[x][z], DP[z][x], DP[z][y], DP[y][z])
	SCMAX = SCMAX2
DP[D][D] += 1
DPANS = 0
for d in DP:
	DPANS = max(max(d), DPANS)
print(ANS + DPANS)


N = int(input())
A = list(map(int, input().split()))
I = 2 * N
D = [[-I] * (N + 1) for _ in range(N + 1)]
M = 0
r = [-I] * (N + 1)

def c(i, j, k):
	D[i][j] = max(k, D[i][j])
	D[j][i] = max(k, D[j][i])
	r[i] = max(r[i], D[i][j])
	r[j] = max(r[j], D[i][j])
	global M
	M = max(M, k)
a = 0
X = A[0]
Y = A[1]
D[X][Y] = 0
D[Y][X] = 0
r[X] = 0
r[Y] = 0
for i in range(N - 1):
	n = A[3 * i + 2:3 * i + 5]
	C = []
	if len(set(n)) == 1:
		a += 1
		continue
	if len(set(n)) == 2:
		for j in range(3):
			if n.count(n[j]) == 2:
				X = n[j]
			else:
				Y = n[j]
		for j in range(1, N + 1):
			C.append((j, Y, D[X][j] + 1))
	(X, Y, Z) = n
	C.append((X, Y, max(M, D[Z][Z] + 1)))
	C.append((Y, Z, max(M, D[X][X] + 1)))
	C.append((X, Z, max(M, D[Y][Y] + 1)))
	for j in range(1, N + 1):
		for k in range(3):
			C.append((j, n[k], r[j]))
	for (j, k, l) in C:
		c(j, k, l)
M = max(M, D[A[-1]][A[-1]] + 1)
print(a + M)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
a.append(n + 1)
a.append(n + 1)
dp = [[-1] * (n + 2) for i in range(n + 2)]
ma = [-1] * (n + 2)
dp[a[0]][a[1]] = 0
ma[a[0]] = 0
ma[a[1]] = 0
after = 0
for i in range(n):
	(x, y, z) = (a[3 * i + 2], a[3 * i + 3], a[3 * i + 4])
	if x == z:
		(y, z) = (z, y)
	if y == z:
		(x, z) = (z, x)
	if x == z:
		after += 1
		continue
	tank = []
	if x != y:
		for i in range(n + 1):
			tank.append((i, x, ma[i]))
			tank.append((i, y, ma[i]))
			tank.append((i, z, ma[i]))
		tank.append((x, y, max(max(ma), dp[z][z] + 1)))
		tank.append((x, z, max(max(ma), dp[y][y] + 1)))
		tank.append((y, z, max(max(ma), dp[x][x] + 1)))
	else:
		for i in range(n + 1):
			tank.append((i, x, ma[i]))
			tank.append((i, y, ma[i]))
			tmp = ma[i]
			if dp[i][x] != -1:
				tmp = max(tmp, dp[i][x] + 1)
			if dp[x][i] != -1:
				tmp = max(tmp, dp[x][i] + 1)
			tank.append((i, z, tmp))
		tank.append((x, y, max(max(ma), dp[z][z] + 1)))
		tank.append((x, z, max(max(ma), dp[y][y] + 1)))
		tank.append((y, z, max(max(ma), dp[x][x] + 1)))
	for (p, q, c) in tank:
		dp[p][q] = max(dp[p][q], c)
		ma[p] = max(ma[p], c)
		ma[q] = max(ma[q], c)
res = 0
for i in range(n + 2):
	for j in range(n + 2):
		res = max(res, dp[i][j])
print(res + after)


import sys
from sys import stdin
N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))
for i in range(3 * N):
	A[i] -= 1
nmax = 0
maxin = [float('-inf')] * N
three = 0
dp = [[float('-inf')] * N for i in range(N)]
(c1, c2) = A[:2]
if c1 > c2:
	(c1, c2) = (c2, c1)
dp[c1][c2] = 0
maxin[c1] = 0
maxin[c2] = 0
for i in range(N - 1):
	cards = A[2 + 3 * i:5 + 3 * i]
	cards.sort()
	if cards[0] == cards[1] and cards[1] == cards[2]:
		three += 1
		continue
	change = []
	if cards[0] == cards[1]:
		nc = cards[0]
		for i in range(N):
			c1 = cards[2]
			c2 = i
			if c1 > c2:
				(c1, c2) = (c2, c1)
			if nc <= i:
				change.append((c1, c2, dp[nc][i] + 1))
			else:
				change.append((c1, c2, dp[i][nc] + 1))
	if cards[1] == cards[2]:
		nc = cards[1]
		for i in range(N):
			c1 = cards[0]
			c2 = i
			if c1 > c2:
				(c1, c2) = (c2, c1)
			if nc <= i:
				change.append((c1, c2, dp[nc][i] + 1))
			else:
				change.append((c1, c2, dp[i][nc] + 1))
	c1 = cards[1]
	c2 = cards[2]
	change.append((c1, c2, dp[cards[0]][cards[0]] + 1))
	c1 = cards[0]
	c2 = cards[2]
	change.append((c1, c2, dp[cards[1]][cards[1]] + 1))
	c1 = cards[0]
	c2 = cards[1]
	change.append((c1, c2, dp[cards[2]][cards[2]] + 1))
	c1 = cards[0]
	c2 = cards[1]
	change.append((c1, c2, nmax))
	c1 = cards[1]
	c2 = cards[2]
	change.append((c1, c2, nmax))
	c1 = cards[0]
	c2 = cards[2]
	change.append((c1, c2, nmax))
	for c1 in cards:
		for c2 in range(N):
			tmpmax = maxin[c2]
			if c1 > c2:
				change.append((c2, c1, tmpmax))
			else:
				change.append((c1, c2, tmpmax))
	for (c1, c2, tmp) in change:
		nmax = max(nmax, tmp)
		dp[c1][c2] = max(dp[c1][c2], tmp)
		maxin[c1] = max(maxin[c1], tmp)
		maxin[c2] = max(maxin[c2], tmp)
nmax = max(nmax, dp[A[-1]][A[-1]] + 1)
print(nmax + three)


from typing import List

class DP:
	N: int
	table: List[List[int]]
	max_all: int
	max_arr: List[int]
	inc: int

	def __init__(self, N: int, x: int, y: int):
		self.N = N
		self.table = [[-(1 << 28)] * (N + 1) for _ in range(N + 1)]
		self.table[x][y] = self.table[y][x] = 0
		self.max_all = 0
		self.max_arr = [-(1 << 28)] * (N + 1)
		self.max_arr[x] = self.max_arr[y] = 0
		self.inc = 0

	def update(self, p: int, q: int, r: int) -> None:
		if p == q == r:
			self.inc += 1
			return
		npqr = self._update_pqr(p, q, r)
		nqrp = self._update_pqr(q, r, p)
		nrpq = self._update_pqr(r, p, q)
		npq = self._update_pq(p, q)
		nqr = self._update_pq(q, r)
		nrp = self._update_pq(r, p)
		np = self._update_p(p)
		nq = self._update_p(q)
		nr = self._update_p(r)
		(pq, qr, rp) = (None, None, None)
		if p == q:
			pq = self._update_pair(p, r)
		if q == r:
			qr = self._update_pair(q, p)
		if r == p:
			rp = self._update_pair(r, q)
		self._update_maximum(q, r, npqr)
		self._update_maximum(r, p, nqrp)
		self._update_maximum(p, q, nrpq)
		self._update_maximum(p, q, npq)
		self._update_maximum(q, r, nqr)
		self._update_maximum(r, p, nrp)
		for k in range(self.N + 1):
			self._update_maximum(k, p, np[k])
			self._update_maximum(k, q, nq[k])
			self._update_maximum(k, r, nr[k])
		if pq:
			for k in range(self.N + 1):
				self._update_maximum(k, r, pq[k])
		if qr:
			for k in range(self.N + 1):
				self._update_maximum(k, p, qr[k])
		if rp:
			for k in range(self.N + 1):
				self._update_maximum(k, q, rp[k])

	def _update_maximum(self, x: int, y: int, v: int) -> None:
		self.table[x][y] = self.table[y][x] = max(self.table[x][y], v)
		self.max_all = max(self.max_all, v)
		self.max_arr[x] = max(self.max_arr[x], v)
		self.max_arr[y] = max(self.max_arr[y], v)

	def _update_pair(self, p: int, q: int) -> List[int]:
		return [max(self.table[k][q], self.table[k][p] + 1, self.table[p][k] + 1) for k in range(self.N + 1)]

	def _update_pqr(self, p: int, q: int, r: int) -> int:
		return max(self.table[q][r], self.table[p][p] + 1)

	def _update_pq(self, p: int, q: int) -> int:
		return max(self.table[p][q], self.max_all)

	def _update_p(self, p) -> List[int]:
		return [max(self.table[p][k], self.table[k][p], self.max_arr[k]) for k in range(self.N + 1)]

	def ans(self):
		return self.max_all + self.inc
N = int(input())
A = list(map(int, input().split())) + [0, 0]
dp = DP(N, A[0], A[1])
for i in range(N):
	Z = A[3 * i + 2:3 * i + 5]
	dp.update(Z[0], Z[1], Z[2])
print(dp.ans())