题目背景

戴夫正在巨浪沙滩的海里游泳，不巧的是此时发生了退潮，伴随退潮的还有“一大波僵尸来袭”！万幸的的是你携带了很多强力植物。眼看僵尸靠近了戴夫，戴夫给你下达了种植植物的命令：“Waibibabu wavero ...”。可惜事发突然，潘妮不在你身旁，无法给你提供戴夫语的翻译。为了拯救戴夫，你必须立刻翻译出来他说的话！

题目描述

戴夫说的话是一个长度为 $n$ 且只包含小写字母的字符串 $S$。此外，戴夫所说的话还包括一个整数 $op$，一个长度为 $n$ 的混乱值数组 $h$，一个长度为 $n$ 的信息量数组 $D$ 和一个长度为 $n$ 的珍贵值数组 $V$，三个数组均由正整数构成。

我们给出一些定义：

设字符串 $A$，我们用 $f_k(A)$ 表示 $A$ 长度为 $k$ 的前缀。

设字符串 $B,C$，我们用 $\operatorname{SET}(B,C)$ 表示既是 $B,C$ 公共后缀又是 $S$（输入字符串）的前缀的字符串所组成的集合。

设字符串 $D$，我们用 $|D|$ 表示字符串 $D$ 的长度。

设逻辑命题 $E$，当 $E$ 成立时 $[E]$ 为 $1$，否则为 $0$。

我们称 $\operatorname{ABS}(x)$ 为整数 $x$ 的绝对值。

你需要求出以下式子的值：

$$\sum_{i=1}^n\sum_{j=i+1}^n \{[\operatorname{ABS}(h_i-h_j)\le op]\times(D_i+D_j)\times\max_{C\in \operatorname{SET}(f_i(S),f_j(S))}V_{|C|}\}$$

特别的，如果 $\operatorname{SET}(f_i(S),f_j(S))$ 为空集，$\max_{C\in \operatorname{SET}(f_i(S),f_j(S))}V_{|C|}$ 为 $0$。

输入格式

第一行两个正整数分别为 $n$，$op$；

第二行一个长度为 $n$ 的字符串 $S$；

第三行 $n$ 个正整数，第 $i$ 个正整数为 $h_i$；

第四行 $n$ 个正整数，第 $i$ 个正整数为 $D_i$；

第五行 $n$ 个正整数，第 $i$ 个正整数为 $V_i$。

输出格式

输出一个非负整数表示答案。

样例1输入

6 2
ababab
1 1 3 3 5 5
2 3 3 2 2 2
6 2 1 3 4 5

样例1输出

82

子任务

对于所有数据，保证 $op\leq n\leq200000$，$h_i\leq n$，$D_i\leq3000$，$V_i\leq 3000$。

测试点编号	$n \leq$	特殊性质
$1 \sim 2$	100
$3 \sim 5$	500
$6 \sim 8$	5000
$9 \sim 10$	200000	$AB$
$11 \sim 1 2$		$A$
$13 \sim 14$		$B$
$15 \sim 16$		$C$
$17 \sim 20$

特殊性质 $A$：$D_i=1$。

特殊性质 $B$：$op=n$。

特殊性质 $C$:字符串仅由 a、b 两种字符构成。