#1134. ddd的回文串

回文串指的是正着读和反着读一样的串，比如 "abcba" 和 “ddd” 都是回文串，但 "cyyakwzk" 不是。

ddd 现在获得了一个长度为 $n$ 的、由小写字母组成的字符串 $s$。wzk 给了他 $m$ 个转换器，第 $i$ 个转换器拥有参数 $x_i, y_i, c_i$，表示 ddd 可以用这个转换器将任意位置的字母 $x_i$ 以 $c_i$ 的代价变成 $y_i$。同时 cyy 还给了他一个超级转换器，表示他可以以 $T$ 的代价，将任意一个字母变为任意另外一个字母。

ddd 对回文串情有独钟，所以他给出了 $n - k + 1$ 个独立的询问，第 $j$ 个询问表示：如果想把 $s$ 中，以 $j$ 开始的、长度为 $k$ 的子串变为回文串，需要的最小代价是多少。ddd 认为回答这个问题太麻烦了，想委托你告诉他这些询问的答案之和是多少。

第一行四个整数 $n, m, k, T$，意义如上所述。

接下来一行，为一个长度为 $n$ 的字符串 $s$，意义如上所述。

接下来 $m$ 行，每行三个元素 $x, y, c$，意义如上所述。

一行一个整数，表示答案。

样例输入

3 4 2 5
dbd
d b 4
d a 1
a z 1
b z 1

样例输出

6

$1 \leq k \leq n \leq 10^6, 0 \leq m \leq 10^6, 1 \leq T, c \leq 10^9$