A4825 | 散落の字符

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 第二轮游戏的结果。