题意

让你求一个子矩阵，这个子矩阵无限拓展之后，可以让原来的矩阵变成这个无限矩阵的子矩阵，并且要使得cost最小， cost是这个子矩阵的最大值 * (子矩阵宽 + 1) * (子矩阵高 + 1)

思路

很显然，我们要求的矩阵尽量小，因为横向和纵向不相互影响， 那么我们可以横向纵向求最小周期，这样就可以保证矩阵最小

求完最小矩阵的长宽后，我们就要求这个矩阵位于哪里，可以使得矩阵里面的最大值最小，这个就可以出动我们的单调队列的，首先，维护一个单调递减的队列，这样队首就是最大值，然后的话，还得主要超过(宽或者高的）我们就抛弃掉了

代码

/**
 *    author: andif
 *    created: 23.06.2023 01:13:28
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

vi get_next(const string& s) {
    int n = sz(s) - 1;
    vi next(n + 1, 0);
    rep(i, 2, n + 1) {
        int j = i - 1;
        while(j && s[i] != s[next[j] + 1]) j = next[j];
        if (j) next[i] = next[j] + 1;
    }
    return next;
}

int gao(const vector<string>& s) {
    int n = sz(s[1]) - 1;
    int ret = n;
    vi cnt(n + 1);
    rep(i, 1, sz(s)) {
        const string& si = s[i];
        vi next = get_next(si);
        int j = n;
        while(j) {
            cnt[n - next[j]]++;
            j = next[j];
        }
    }
    rep(i, 1, n + 1) {
        // dd(i), de(cnt[i]);
        if (cnt[i] == sz(s) - 1) {
            ret = i;
            break;
        }
    }
    return ret;
}

int main() {
    qc;
    int n, m; cin >> n >> m;
    vector<string> s(n + 1);
    rep(i, 1, n + 1) {
        cin >> s[i];
        s[i] = '#' + s[i];
        // dd(i), de(s[i]);
    }
    vector<string> t(m + 1);
    rep(i, 1, m + 1) {
        string tmp = "#";
        rep(j, 1, n + 1) {
            tmp += s[j][i];
        }
        t[i] = move(tmp);
        // dd(i), de(t[i]);
    }
    vector<vi> a(n + 1, vi(m + 1, 0));
    rep(i, 1, n + 1) rep(j, 1, m + 1) cin >> a[i][j];

    // auto check = [&] (int x, int p, int q) {
    //     vector<vi> b(n + 1, vi(m + 1, 0));
    //     rep(i, 1, n + 1) rep(j, 1, m + 1) {
    //         b[i][j] = a[i][j] > x ? 1 : 0;
    //     }
    //     rep(i, 1, n + 1) rep(j, 1, m + 1) b[i][j] += b[i][j - 1];
    //     rep(j, 1, m + 1) rep(i, 1, n + 1) b[i][j] += b[i - 1][j];
    //     rep(i, 1, n + 1) rep(j, 1, m + 1) {
    //         int ni = i + q - 1, nj = j + p - 1;
    //         if (ni > n || nj > m) continue;
    //         int value = b[ni][nj] - b[ni][j - 1] - b[i - 1][nj] + b[i - 1][j - 1];
    //         if (!value) return true;
    //     }
    //     return false;
    // };

    int p = gao(s), q = gao(t);
    // dd(p), de(q);
    // int l = 0, r = 1e9;
    // while(l + 1 < r) {
    //     int mid = (l + r) >> 1;
    //     if (check(mid, p, q)) {
    //         r = mid;
    //     } else {
    //         l = mid;
    //     }
    // }
    // ll ans = check(l, p, q) ? l : r;
    ll ans = 1e9;
    deque<int> dq;
    auto b = a;
    rep(i, 1, n + 1) {
        while(sz(dq)) dq.pop_back();
        rep(j, 1, m + 1) {
            while(sz(dq) && j - dq.front() + 1 > p) dq.pop_front();
            while(sz(dq) && a[i][dq.back()] <= a[i][j]) dq.pop_back();
            dq.push_back(j);
            b[i][j] = a[i][dq.front()];
        }
    }

    rep(j, 1, m + 1) {
        while(sz(dq)) dq.pop_back();
        rep(i, 1, n + 1) {
            while(sz(dq) && i - dq.front() + 1 > q) dq.pop_front();
            while(sz(dq) && b[dq.back()][j] <= b[i][j]) dq.pop_back();
            dq.push_back(i);
            if (i >= q && j >= p)
                ans = min(ans, 1ll * b[dq.front()][j]);
        }
    }
    ans = ans * (p + 1) * (q + 1);
    cout << ans << '\n';
    return 0;
}