A45678.散落の字符

FM 正在和 MW 玩一个似乎不怎么有趣的大型游戏。

游戏规则是这样的：FM 有一个大小为 $N\times M$ 的迷宫，特殊的，这个迷宫里全部都是数字，表示经过这一格的花费。FM 要求 MW 在迷宫中选取一条线路从 $(1,1)$ 到 $(N,M)$，但是这条线路必须是通过这个迷宫总花费最小的方法。等到达迷宫的 $(N,M)$ 格时，记该迷宫的花费为 $10^{\min_a}$。某条线路的总花费是指它经过格子上花费的总和。

接下来是第二轮游戏：FM 找到之前出数据时的字符串 $s,t$（这是两串没有规律的数据，且 $s$ 均为小写字母， $t$ 为任意小于 $10$ 的正整数，当 $t$ 介于 $1$ 和 $9$ 之间时看作 $1$），将上一个游戏的结果 $10^{\min_a}$ 一个数字一个数字地划开，以 $1$ 表示 a，$2$ 表示 b，$3$ 表示 c，……，$9$ 表示 i 的方式补充字母到字符串 $s$ 之后。特别地，当划分时遇到的数字的结果是 $0$ 时，将当前字符串 $s$ 的最后一个字母复制一份到字符串 $s$ 的末尾处。然后将里边的字母变为其 ASCII 码值对 $2$ 取模，并为其赋权 $w_i$，最后在 $t$ 的末尾加上 $s$（这一步仅改变 $t$，不改变 $s$）。

在 $s$ 的构建完成后，到了 MW 的部分：你需要先得出 $t$ 中的最长回文串长度 $l$，然后对 $s$ 进行若干次反转操作（$0$ 变 $1$ 或者 $1$ 变 $0$），反转第 $i$ 位需要花费 $w_i$ 的代价。请你使用最小代价 $f$ 把 $s$ 变成一个偶回文串，请输出最小总代价 $f$ 与 $l$ 的和。

输入共 $N+4$ 行：

第一行两个正整数 $N$ 和 $M$，表示迷宫的大小；

接下来 $N$ 行每行 $M$ 个正整数，表示经过该格的花费 $a_{i,j}$；

然后两个字符串 $s,t$，最后 $1$ 行 $|s|+\lfloor \min_a \rfloor + 1$ 个整数表示 $s_i$ 的权重 $w_i$。

输出共 $1$ 行：

输出一个正整数表示 MW 第二轮游戏的结果。

下面记字符串 $s$ 和 $t$ 的长度为 |$s$| 和 |$t$|。

对于所有的数据，保证：

$1\le N,M\le15$
$1\le a_{i,j},w_i\le10^9$，$1\le|s|,|t|\le2 \times 10^5$
$2\ |\ (|$s$|+\lfloor \min_a \rfloor + 1)$

字符串 $s$ 中均为小写字母，数据保证可以把 $s$ 变成偶回文串。

测试点	|$s$| , |$t$| $\le$
1,2	$50$
3,4,5	$10^3$
6~20	$2 \times 10^5$

本题测试点等分。

【样例解释】

样例组 #1：有一个大小为 $3\times3$ 的迷宫，通过这个迷宫的最小花费方式是 $(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)$（先行后列），花费 $10^{\min_a}$ 为 $16$。将 $16$ 一位一位地分解成字母为 af，拼接在原来的字符串 $s$ 后为：afafafafaf，变换数字后为 1010101010。通过枚举可得最小总代价为 $5$（一种方式是改变后边的五位使原字符串变为1010110101,本身为偶回文串），然后此时 $t$ 为 011010101010，最长回文串长度为 $9$（101010101），$9 + 5 = 14$，输出 $14$。