有 $n$ 张扑克堆成一个栈，从上往下第 $i$ 张价值是 $V_i$，此外有花色$C_i$和点数$A_i$。

有这样一个操作，每次可以选择拿走栈中从上往下第 $1$ 张或者第 $3$ 张。

除了第一次，每次拿走一张牌时，它必须和上一张牌的"花色或点数"相等。随时可以停止拿牌。

请问如何拿牌，才能使得拿出来的牌的价值和最大。

输入格式

第一行包含一个整数 $ N $，表示牌的个数。

接下来 $ N $ 行，第 $ i $ 行包含三个整数 $ C_i $，$ A_i $ 和 $ V_i $，表示从上往下第 $ i $ 张花色是 $ C_i $，点数是 $ A_i $，价值是 $ V_i $。

输出格式

输出一个整数表示最大价值和。

样例输入

5
1 3 2
4 2 9
1 4 6
2 3 3
2 2 1

样例输出

15

数据范围

• sub1(10pts):$n\leq 20$
• sub2(20pts):$n\leq 100$
• sub3(30pts):$n\leq 500$
• sub4(40pts):$n\leq 1919$

$C_i,A_i\in[1,n];V_i\in[1,10^6]$

$2s,512MB$