安娜经常和朋友布鲁诺玩纸牌游戏，但她对两人玩的游戏感到厌倦，于是想出了一个可以独自一人玩的纸牌游戏。

游戏开始时，有 $N$ 张不同颜色的纸牌排成一列，每张牌上写有一个整数。每张牌的颜色用一个整数表示。此外，每张牌都有一个固定的价值。游戏开始时，从列的开头数第 $i$ 张 ($1 \le i \le N$) 牌的颜色为 $C_i$，上面写的整数为 $A_i$，其价值为 $V_i$。

游戏通过重复从牌列中选出一张牌并将其加入牌堆的操作来进行。起初，牌堆中没有牌，从该状态开始，安娜重复执行以下操作：

• 操作：从牌列的开头选择第 1 张或第 3 张牌。但是，如果在执行操作前牌堆中已经有牌，则只能选择那些与牌堆最顶端的牌在颜色或所写整数上至少有一项一致的牌。将选中的牌从列中移除，并将其加到牌堆的最顶端。

当无法通过操作选择任何牌时，游戏结束。游戏结束时，牌堆中所有牌的价值总和即为安娜的得分。

请问安娜在这个游戏中能获得的最高得分是多少？

题目描述

给定游戏开始时排列的纸牌信息，编写一个程序，求出安娜在这个游戏中能获得的最高得分。

输入格式

从标准输入读取以下数据：

• 第 1 行包含一个整数 $N$，表示游戏开始时排列的纸牌数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含三个空格分隔的整数 $C_i, A_i, V_i$，表示游戏开始时从列开头数第 $i$ 张牌的颜色为 $C_i$，所写整数为 $A_i$，价值为 $V_i$。

输出格式

将安娜在该游戏中能获得的最高得分作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 500$
• $1 \le C_i \le 500$ ($1 \le i \le N$)
• $1 \le A_i \le 500$ ($1 \le i \le N$)
• $1 \le V_i \le 1\,000\,000$ ($1 \le i \le N$)

子任务

• 子任务 1 [10 分]：满足 $N \le 20$。
• 子任务 2 [15 分]：满足 $N \le 50$。
• 子任务 3 [75 分]：无额外限制。

样例

输入样例 1

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

输出样例 1

15

说明

将颜色为 $c$，所写整数为 $a$，价值为 $v$ 的牌表示为 $(c, a, v)$。 通过按以下方式进行游戏，安娜可以获得最高得分：

1. 从列的开头取第 1 张牌 $(1, 3, 2)$ 放入牌堆，获得 2 分。
2. 从列的开头取第 3 张牌 $(2, 3, 3)$ 放入牌堆，获得 3 分。
3. 从列的开头取第 3 张牌 $(2, 2, 1)$ 放入牌堆，获得 1 分。
4. 从列的开头取第 1 张牌 $(4, 2, 9)$ 放入牌堆，获得 9 分。

输入样例 2

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

输出样例 2

160