一个字符串如果从左到右和从右到左读的结果是一样的，我们称之为回文串。现在给定一个字符串，我们有三种操作：

1.     添加一个字母在任何位置(可以在首尾添加) (add ‘*’)

2.     删除一个字母 (erase ‘*’)

3.     改变一个字母变成另外一个字母 (change ‘*’ to ‘*’)

然而，这些操作可以改变的字母是由longpo指定的。比如，longpo指定可以删除字母’a’，添加字母’b’，改变字母’d’。没指定的操作其他的字母不可以改变。

另外，每个操作需要有代价，因此，这三个操作可以描述为：

1.     “add c x”

2.     “erase c x”

3.     “change c1 c2 x”

分别表示增加字母c需要x的代价，删除字母c需要x的代价，改变c1变成c2需要x的代价。

现在给你一个字符串，然后n个操作，问你最少需要多少代价将这个字符串变成回文串，输出最小代价。如果不能变成回文串，则输出”-1”。

输入一个长度为 $m$ 的字符串，全部由小写字母组成。

输入操作数量 $n$，然后输入 $n$ 个操作。