星际旅行

题目描述

在游遍地球之后， 姥姥开始计划星际旅行了。 她收集了所有中转空间站的容量， 然后需要计算一下， 一颗星球得有多大的容量， 才能保证每一艘宇宙飞船在到达星球时能卸下全部旅客。

时间限制： 1000 内存限制： 262144

输入

输入在第一行给出出发星球和目 的地星球的名称， 以及一个正整数 n（≤ 500） 。 

随后 n 行， 每行格式为： 出发地目的地 容量其中 `出发地` 和 `目的地` 是中转空间站或者上面给出的两个星球的名称， 每个名称都是由 3 个大写英文字母组成的。 

`容量` 是从 `出发地` 到 `目的地` 飞船一次能运送的最多人数，是个正整数。

 注意： 中转空间站没有接待旅客住宿的条件， 旅客无法驻留， 必须立刻全部转去下一站。 所以中转空间站不能允许超过其最大容量的飞船停靠， 即接收多少人就必须送出多少人。 

题目保证没有包括任何从目 的地飞出的航线信息， 也没有飞到出发地的航线信息。

输出

在一行中输出目的地星球必须具备的最小容量， 使得所有到达的飞船都能停靠卸载所有旅客。

样例输入

EAR MAR 11

EAR AAA 300

EAR BBB 400

AAA BBB 100

AAA CCC 400

AAA MAR 300

BBB DDD 400

AAA DDD 400

DDD AAA 100

CCC MAR 400

DDD CCC 200

DDD MAR 300

样例输出

700