题目描述

安娜与朋友布鲁诺玩过卡牌游戏，但两人对双人游戏感到厌倦，于是她设计了一款可单人游玩的卡牌游戏。

游戏开始时，有 $N$ 张不同颜色的卡牌排成一行，每张卡牌上写有一个整数。每张卡牌的颜色用整数表示，每张卡牌也有一个固定的价值。在游戏开始时，从队列前端起第 $i$ 张卡牌（$1 \le i \le N$）的颜色为 $C_i$，写在上面的整数为 $A_i$，其价值为 $V_i$。

游戏通过从卡牌序列中逐张选取卡牌并将其加入牌堆来进行。初始时牌堆为空，从该状态开始，安娜重复以下操作：

• 操作：从卡牌序列的前端选择第 1 张或第 3 张卡牌。但若操作前牌堆中已有卡牌，则只能从序列中选择一张与牌堆最上方卡牌颜色相同，或写有相同整数的卡牌。选出的卡牌从序列中移除，并添加到牌堆的最上方。

当无法再选择任何卡牌时，游戏结束。游戏结束时，山堆中所有卡牌的价值之和即为安娜的得分。

问：在此游戏中，安娜能够获得的最大得分是多少？

题目

给定游戏开始时排列的卡牌信息，编写程序求出安娜在该游戏中可能获得的最大得分。

输入格式

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

• 第一行包含一个整数 $N$，表示游戏开始时排列的卡牌数量。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含三个整数 $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 解释

将颜色为 $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 分。

数据范围

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

• $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 1000000$（$1 \le i \le N$）

子任务

子任务 1 [10 分]

满足以下条件：

• $N \le 20$

子任务 2 [15 分]

满足以下条件：

• $N \le 50$

子任务 3 [75 分]

无额外限制。

翻译由 Qwen3-235B 完成