题目描述

译自 JOISC 2015 Day3 T2「Card Game Is Great Fun」。

有 $N$ 张扑克堆成一个栈，从上往下第 $i$ 张花色是 $C_i$，点数是 $A_i$，价值是 $V_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

8
11 5 31
2 8 19
2 9 2
11 8 45
4 8 22
4 2 23
6 9 58
6 2 5

160

数据范围与提示

对于全部数据，满足 $ 1 \le N \le 500, 1 \le C_i, A_i \le 500, 1 \le V_i \le 10^6$。

本题共有 $3$ 个子任务。每个子任务的分数和附加限制如下：