题目描述

在一处古老的文明遗址中，考古队发现了大量破碎的文物残片。这些残片形状各异，且表面刻有不同图案和符号。考古学家们希望通过拼接这些残片，还原出完整的文物，从而揭开古代文明的神秘面纱，已知现场共有$N$块文物残片,每块残片都有独特的形状轮和文化价值。为了完成拼接，必须遵循以下规则:

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

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

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

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

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

输入格式

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

输出格式

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

输入输出样例

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

80

样例解释

最优拼接方案为：起始残片（分值 20）→ X01 Y02（分值 20）→ Y02 Z03（分值 15）→ Z03 C04（分值 25），总分为 $20 + 20 + 15 + 25 = 80$ 分。