测试数据来自 zxshy/1002

打表提示

输出0,得30分。

题目背景

中士想到了一道绝世好题。

题目描述

中士准备为这道绝世好题加上一个绝世好标题。但是他的语文超级无敌差，想了两年半也没想到这个绝世好标题，只想到了 \(n\) 个词语。根据一些基本的语文语法可得知 \(m\) 个词语关系，形如 \(x(我是空格) y(我是空格)t\) ，意思是 \(y\) 词可以放在 \(x\) 后面，并且这种连接能增加 \(t\) 的分数。一个标题的总分数就是它所有连接的分数之和。他想问你，他能写出的最好的标题分数多高？
又经过了两年半的思考，他发现这个问题对你实在是太难了(实际上是因为出题人T了)，所以他帮你确定了第一个词语 \(s\) 。现在，他再次问你，他能写出的最好的标题分数多高？

数据样例

输入

第一行， \(n\) , \(m\) 和 \(s\) 。
接下来 \(n\) 行，是每个词语。
接下来 \(m\) 行，是如题所说的连接。

输出

一个数字，是中士让你算的数字。

样例1

输出

5 4 iam
iam
s
is
a
b
iam a 10
a s 10
s b 10
is a 1

输出

30

样例2

输入

4 4 IOI
IOI
I
ME
AK
IOI AK -1
AK ME 100
IOI ME 50
AK I 1

输出

99

提示

第一个样例最佳为iam-a-s-b，第二个样例最佳为IOI-AK-ME。
关于范围...爆不了int...\(n^3\) 能过...(然而是个稠密图)。
样例无重复词语，无重复边，每个词语只能用一次。

提示*2

\(\small\color{white}朴素最大生成树的都去过第二个样例！！！\)