问题1239--回文串

1239: 回文串

[命题人 : ]
时间限制 : 1.500 sec  内存限制 : 128 MB

题目描述

题目背景

Rolnan在研究回文串了,但是简单的回文串显然无法引起Rolnan的兴趣,因此他希望更深入研究回文串。

题目描述

Rolnan有一串长度为 \(n(1\leq n\leq 10^5)\) 的字符串 \(S\),同时他有 \(m(1\leq m \leq 1000)\) 个妙具,每个妙具可以将一个字符 \(a_i\) 转化为字符 \(b_i\) ,但是需要 \(c_i\)的代价。

现在Rolnan想知道,对于所有连续子串 \((\frac{n*(n-1)}{2}个连续子串)\),分别将他们变成回文串的最小代价之和。

Rolnan当然能够很轻松的完成这个任务,但是他刚买了阿克尚,想去操(zuo)作(fan)了,请你来帮助他吧。


输入

第一行两个整数 \(n,m\)。

第二行一个长度为 \(n\) 的字符串 \(S\)。

接下来$m$行,每行两个小写字母 \(a_i,b_i\) 和一个整数 \(c_i\) ,用空格分开。

输出

一个整数表示最小代价和。

样例输入 Copy

5 2
aabaa
a b 1
b a 10

样例输出 Copy

6

提示

\(1\leq n\leq 10^5,1\leq m\leq 1000,1\leq c_i\leq 10^4,a_i,b_i,S_i\) 均为小写字母。

数据保证对于所有出现的字符,任意两个字符间可以互相转化。

对于样例,其中连续子串 \(aab,aaba,ab,abaa,ba,baa\) 都不是回文串,每个的最小贡献是1,因此总的贡献是6。