题号：NC21337
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
牛牛喜欢回文串，牛妹给了牛牛一个字符串S，牛牛想把S变成回文串
牛牛可以做如下三种操作
1：在任意位置增加一个字符
2：删除一个字符
3：改变一个字符
每种操作都有限定的字符，比如，只能删除'a',增加'b',把'c'变成'd'等等
每种操作都有相应的代价
用M条语句来描述能进行的操作
add c x 表示增加c字符需要x的代价
erase c x表示删除c字符需要x的代价
change c1 c2 x表示将c1 改成c2需要x的代价
求牛牛想要得到回文串需要的最少代价
如果不行输出-1
输入描述:
第一行输入一个字符串S(都是小写字母)表示牛妹给牛牛的串(1 ≤ |S| ≤ 50)
第二行输入一个整数m (0 ≤ m ≤ 50)
接下来m行的格式是
add c x
erase c x
change c1 c2 x
三种中的一种
c c1 c2都是小写字母
1 ≤ x ≤ 100000
所有允许的操作去除x部分后都是不同的
输出描述:
输出一个整数
示例2
输入
复制
caaaaaab
6
change b a 100000
change c a 100000
change c d 50000
change b e 50000
erase d 50000
erase e 49999
示例3
输入
复制
moon
6
erase o 5
add u 7
change d p 3
change m s 12
change n d 6
change s l 1
示例4
输入
复制
xab
7
change a c 1
change b d 1
change c e 1
change d e 1
add y 1
change y z 1
change x z 1
备注:
子任务1: |S| <= 10
子任务2: |S| <= 20
子任务3: 无限制