#9009. 「第8次PTA认证」考古遗址的文物拼接 普及/提高−

在一处古老的文明遗址中，考古队发现了大量破碎的文物残片。这些残片形状各异，且表面刻有不同图案和符号。考古学家们希望通过拼接这些残片，还原出完整的文

物，从而揭开古代文明的神秘面纱，已知现场共有N块文物残片,每块残片都有独特的形状轮和文化价值。为了完成拼接，必须遵循以下规则:

1.拼接规则:后一块残片的起始边缘形状必须与前一块残片的结束边缘形状完全匹配。每块残片都标注了首尾边缘的形状代码(如A01、B05等)。

2.价值计算:每块残片根据其保存完整度和历史意义，被赋予了不同的文化价值分(范围1-100)。成功拼接的残片组合，其总价值为各残片价值之和。

3.特殊限制:每块残片只能使用一次，且拼接过程不可逆考古实习生小周负责本次拼接任务，他拿到了一块起始残片，其首尾边缘形状代码已确定。现在他需要从N块候

选残片中，规划出总价值最高的拼接方案，以最大程度还原文物的历史价值。

注意:请你帮助小周计算，他能获得的最高累计文化价值是多少?

1.第一行:一个字符串和一个整数,分别表示起始残片的结束边缘形状代码(长度不超过8位)和起始残片的文化价值。

2.第二行:整数 ()，表示候选残片数量。

3.接下来 行，每行格式为起始边缘代码、结束边缘代码、分值(分值为100的整数)，例如“A02 B03 30”。

一个整数，表示小周能获得的最高累计文化价值(包含起始残片分值，若无法拼接则输出起始残分值)。

样例输入

X01 20
4
X01 Y02 20
Y02 Z03 15
A01 B02 10
Z03 C04 25

样例输出

80

样例解释

最优拼接方案为:起始残片(自带分值) → X01 Y02 → Y02 Z03 → Z03 C04，总分为20(起始)+20+15+25=80 分。

形状代码由字母或数字组成，无重复代码。 数据:; 数据: 。