题目描述
在离太阳系很遥远的一个星球上，有一些奇特的物种，名为OIer
他们的遗传物质叫AC，类似于人类的DNA
AC也是链状的，但AC有头尾之分
组成AC的单体有26种，分别名为WA,TLE,RE,MLE,CE,PE,OLE,UKE......
为了方便表示，这里将这26中单体用26个小写字母表示
现在OIer们正在研究AC：
如何用最少的花费将一串AC变成另一串AC
现在OIer们有以下技术：
01：对于一串AC，可从尾部逐个删除单体，不需要任何花费
10：对于任何一个位置的单体，可以经过一些变化变成想要的单体，花费为所有变化的
总花费，变化规则OIer已经研究透了
11：对于一串AC，可以从尾部逐个添加任意一个单体，当在这串AC尾部第k次添加单体
时花费为k*c
现在给出m个变化规则，每个变化规则x，y，z表示x单体可花费z变成y单体
并有t对AC，每对AC中有两串长度至少为1的AC：s1，s2
对于每对AC，要求将s2变成s1最小花费是多少
又由于OIer超级喜欢二进制，所以最小花费均用二进制数输出
输入
第一行三个整数m t c
接下来m行，每行x y z
接下来2*t行，每行一个字符串，均由小写字母组成，表示一串AC
输出
每读入两串AC（即读入一对AC）
输出将s2变成s1最小花费（前一个为s1，后一个为s2）
2 1 6
a b 2
a c 3
bck
aab