网络流：宇宙旅行

宇宙旅行"/>

网络流：宇宙旅行

1. 题目要求

在走遍了地球上的所有景点以后，旅游狂人开始计划他的宇宙旅行项目。经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数的列表。当旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客驻留，旅客必须立刻转乘另一艘飞船离开，所以空间站不能接待超过自己最大容量的旅客流。为了估计预算，现在旅游狂人需要知道终点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。

2. 输入要求

输入由若干组测试数据组成。
每组测试数据的第一行包含旅行的起点星球和终点星球的名称和一个不超过500的正整数N（N为0标志全部测试结束，不要对该数据做任何处理）。
接下来的N行里，数据格式为：(以下的i为下标)sourcei  destinationi capacityi，其中sourcei和destinationi是卫星空间站的名称或起点、终点星球的名称，正整数capacityi是飞船从sourcei到destinationi一次能运载的最大旅客流量。每个名称是由A~Z之间的3个大写字母组成的字符串，例如ZJU。
测试数据中不包含任何到达起点星球的信息以及任何从终点星球出发的信息。

3. 输出要求：

对每一组测试，在一行里输出终点星球接待站应具有的最小容量，使得每艘飞船在到达时都可以保证让全部旅客下船。

4. 输入例子

EAR MAR 8
EAR AAA 300