PATH

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "PATH"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int mod = 998244353;
const int N = 1e2+5;
const int M = 1e3+5;
const ll base = 257;
const ll base1 = 311;
int n, m, a[M][M], k, res;
vector<int> adj[N];
char c[M][M];
ll dp[N][N][N][N], ans, f[M][M];
int posy(int x, int k, bool down)
{
    if(down)return k-(x-1);
    k = (m+n-1)/2-k+1;
    return m-(k-1-(n-x));
}
void add(ll& x, ll y)
{
    if(x < y)x = y;
}
void add(int step, int lst, int lx, int ly, int rx, int ry, ll v)
{
    if(c[lx][ly] == c[rx][ry])
        add(dp[step][lx][rx][lst], v+a[lx][ly]+a[rx][ry]);
}
void sol(int itest)
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)cin >> c[i][j];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)cin >> a[i][j];
    if(max(n, m) > 100)
    {
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= m; j ++)
            {
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }
        cout << f[n][m];
        return;
    }
    memset(dp, -1, sizeof(dp));
    for(int x = 1; x <= n; x ++)
    {
        int y = posy(x, 1, 0);
        if(1 > y || y > m)continue;
        if(c[1][1] == c[x][y])
            add(dp[1][1][x][x], a[1][1]+a[x][y]);
    }
    ans = -1;
    for(int step = 1; step < (n+m-1)/2; step ++)
    {
        for(int lx = 1; lx <= n; lx ++)
        {
            for(int lst = lx; lst <= n; lst ++)
            {
                for(int rx = lst; rx <= n; rx ++)
                {
                    if(dp[step][lx][rx][lst] == -1)continue;
                    int ly = posy(lx, step, 1), ry = posy(rx, step, 0);
                    if(min(ly, ry) < 1 || max(ly, ry) > m)continue;
                    for(int x1 = lx; x1 <= min(lx+1, lst); x1 ++)
                    {
                        for(int x2 = rx; x2 <= min(rx+1, n); x2 ++)
                        {
                            int y1 = posy(x1, step+1, 1);
                            int y2 = posy(x2, step+1, 0);
                            if(min(y1, y2) < 1 || max(y1, y2) > m)continue;
                            add(step+1, lst, x1, y1, x2, y2, dp[step][lx][rx][lst]);
                        }
                    }
                }
            }

        }
    }
    for(int i = 1; i <= n; i ++)
    {
        ans = max(dp[(m+n-1)/2][i][n][i], ans);
        ans = max(dp[(m+n-1)/2][i][n][i+1], ans);
    }
    cout << ans;
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest;
    ntest = 1;
    //cin >> ntest;
    for(int i = 1; i <= ntest; i ++)
        sol(i);
}