2. 考古遗址的文物拼接

题目描述

在一处古老的文明遗址中，考古队发现了大量破碎的文物残片。每块残片都有独特的形状轮廓和文化价值。拼接规则如下：

1. 后一块残片的起始边缘形状必须与前一块残片的结束边缘形状完全匹配。
2. 每块残片只能使用一次，且拼接过程不可逆。
3. 总价值为各残片价值之和。

现在给定一块起始残片（其结束边缘形状代码和价值）和 (N) 块候选残片（每块包含起始边缘代码、结束边缘代码、分值），要求规划出总价值最高的拼接方案。

输入格式

1. 第一行：一个字符串和一个整数，分别表示起始残片的结束边缘形状代码（长度不超过8位）和起始残片的文化价值。
2. 第二行：整数 (N)（(1 \leq N \leq 50)），表示候选残片数量。
3. 接下来 (N) 行，每行格式为“起始边缘代码 结束边缘代码 分值”。

输出格式

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

样例输入

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

样例输出

80