ac

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int hmod = 1e9 + 7, base = 31;
int n, m, migong[333][333], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
long long w[200025], dp[200010], ret = 1e13;
bool vis[333][333];
char monib[30] = {'0', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
string a, b, c, d, t;
char s[13000000];
int maxs[13000000];

struct Node {
    int x, y, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

void dijkstra() {
    priority_queue<Node> pq;
    pq.push({1, 1, migong[1][1]});
    vis[1][1] = true;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int x = current.x, y = current.y, cost = current.cost;

        if (x == n && y == m) {
            ret = cost;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;
            }
            vis[nx][ny] = true;
            pq.push({nx, ny, cost + migong[nx][ny]});
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> migong[i][j];
        }
    }

    dijkstra();
    a = to_string(ret);
    cin >> b;
    d += b;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == '0') {
            d += d[d.size() - 1];
        } else {
            d += monib[a[i] - '0'];
        }
    }
    for (int i = 0; i < d.size(); ++i) {
        d[i] = ((int)d[i]) % 2 + '0';
    }
    t = d;
    cin >> c;
    c += d;
    int alen = c.size(), len = 2;
    s[0] = '%';
    s[1] = '#';
    for (int i = 0; i < alen; ++i) {
        s[len++] = c[i];
        s[len++] = '#';
    }
    s[len] = '#';
    int mid = 1, r = 1, ans1 = -1;
    for (int i = 1; i <= len; ++i) {
        maxs[i] = 0;
    }
    for (int i = 1; i <= len; ++i) {
        if (i < r) {
            maxs[i] = min(r - i, maxs[mid * 2 - i]);
        } else {
            maxs[i] = 1;
        }
        while (s[i - maxs[i]] == s[i + maxs[i]]) {
            maxs[i] += 1;
        }
        if (r < i + maxs[i]) {
            mid = i;
            r = i + maxs[i];
        }
        ans1 = max(maxs[i] - 1, ans1);
    }
    for (int i = 0; i < t.size(); ++i) {
        cin >> w[i];
    }
    n = t.size();
    for (int i = 0; i < d.size() / 2; ++i) {
        if (d[i] == d[d.size() - i - 1]) continue;
        else ans1 += min(w[i], w[d.size() - i - 1]);
    }
    cout << ans1 << "\n";
    return 0;
}