Subtask 1: ~n = 1~

Ở đây, mảng ~a~ chỉ là một mảng 1D. Đáp án ở đây chính xác là $$\sum_{i=1}^n a_i - \min(a_{i - 1}, a_i)$$ với quy ước rằng ~a_0 = 0~. Để chứng minh công thức này, ta dựng các viên gạch từ trái sang phải. Khi đến ô thứ ~i - 1~, hiện tại đang có ~a_{i - 1}~ viên gạch đang kết thúc ở ô này. Khi qua ô thứ ~i~, ta sẽ chọn kéo dài càng nhiều viên gạch từ ô ~i - 1~ qua ô ~i~ nhất có thể; số lượng viên gạch tối đa có thể kéo dài ở đây là ~\min(a_{i - 1}, a_i)~. Vì thế, số lượng viên gạch mới phải thêm vào và bắt đầu ở ô thứ ~i~ là ~a_i - \min(a_{i - 1}, a_i)~.

Độ phức tạp của subtask này là ~O(n)~.

Subtask 2: ~a_{i, j} \le 1~

Đây là một bài toán cổ điển đã xuất hiện trước đây (ví dụ).

Để giải bài toán trên, ta giả sử ban đầu ta chỉ xếp các gạch có kích thước ~1 \times 1~ — số lượng gạch cần dùng là ~\sum a_{i, j}~. Sau đó, ta sẽ ghép các gạch lại với nhau càng nhiều càng tốt bằng cách xoá tối đa số lượng cạnh giữa các ô gạch, sao cho các thành phần liên thông cuối cùng vẫn thoả mãn là các viên gạch ~k \times 1~ hoặc ~1 \times k~.

Một thành phần như thế là một viên gạch khi và chỉ khi không có hai cạnh tạo hình chữ L được xoá đi cùng lúc. Ta dựng một đồ thị với mỗi đỉnh biểu diễn một cạnh giữa hai ô 1 trong bảng, và một cạnh được nối giữa hai đỉnh biểu diễn hai cạnh trong bảng mà tạo hình chữ L.

Số lượng cạnh tối đa có thể xoá chính xác bằng tập độc lập lớn nhất (maximum independent set) của đồ thị trên. Nhận thấy rằng đồ thị được dựng là đồ thị hai phía; một phía biểu diễn các cạnh dọc, và phía còn lại biểu diễn các cạnh ngang. Vì thế, theo định lý Koenig, độ lớn của tập độc lập tối đa chính xác bằng ~|V|~ - độ lớn của cặp ghép lớn nhất, với ~|V|~ là số lượng đỉnh trong đồ thị trên. Việc dựng đồ thị trên và chạy thuất toán cặp ghép lớn nhất mất độ phức tạp là ~O(mn \sqrt{mn})~ (do đồ thị có ~O(mn)~ đỉnh, với mỗi đỉnh có tối đa 4 cạnh).

Subtask 3: Không có ràng buộc gì thêm

Ta sẽ tổng quát hoá thuật toán ở subtask 2. Gọi ~x_{i, j, 0}~ là số lượng viên gạch được đi ngang qua cạnh ~(i, j) \to (i, j + 1)~, và ~x_{i, j, 1}~ là số lượng viên gạch được đi dọc qua cạnh ~(i, j) \to (i + 1, j)~. Nhận thấy rằng ta muốn tổng ~\sum_{i, j} x_{i, j, 0} + x_{i, j, 1}~ được tối đa nhất có thể; đây chính xác là số lượng lần ta có thể ghép các viên gạch lại với nhau như ở subtask 1 và 2. Đồng thời, ta có một số các giới hạn như sau: ở ô ~(i, j)~,

• Số lượng viên gạch đi ngang qua ~(i, j + 1)~ và số lượng viên gạch đi dọc xuống ~(i + 1, j)~ được tối đa là ~a_{i, j}~: ~x_{i, j, 0} + x_{i, j, 1} \le a_{i, j}~.

• Số lượng viên gạch đi ngang qua ~(i, j - 1)~ và số lượng viên gạch đi dọc xuống ~(i + 1, j)~ được tối đa là ~a_{i, j}~: ~x_{i, j - 1, 0} + x_{i, j, 1} \le a_{i, j}~.

• Số lượng viên gạch đi ngang qua ~(i, j + 1)~ và số lượng viên gạch đi dọc lên ~(i - 1, j)~ được tối đa là ~a_{i, j}~: ~x_{i, j, 0} + x_{i - 1, j, 1} \le a_{i, j}~.

• Số lượng viên gạch đi ngang qua ~(i, j - 1)~ và số lượng viên gạch đi dọc lên ~(i - 1, j)~ được tối đa là ~a_{i, j}~: ~x_{i, j - 1, 0} + x_{i - 1, j, 1} \le a_{i, j}~.

Ngoài ra, ta cũng có một số điều kiện biên, như là ~x_{i, 0, 0} = x_{i, m, 0} = 0~ và ~x_{0, j, 1} = x_{n, j, 1} = 0~ để không có viên gạch nào đi ra khỏi biên. Ta có thể dựng các điều kiện biên này theo như format như trên (ví dụ, ~x_{i, 0, 0} + x_{0, j, 1} \le 0~).

Cuối cùng, ta thu được một linear program ~P_1~ có dạng như sau, với hai phía là ~L~ và ~R~:

$$\text{max} \quad\quad\quad \sum_{i \in L} x_i + \sum_{j \in R} y_j$$ $$\text{sao cho} \quad\quad\quad x_i + y_j \le w_{i, j} \quad \forall (i, j) \in E$$ $$x_i, y_j \ge 0$$

Ta biến đổi bài toán này như sau: gọi ~p_i = \min_{(i, j) \in E} w_{i, j}~ là cạnh nhỏ nhất kề với đỉnh ~i \in L~, và tương tự ~q_j = \min_{(i, j) \in E} w_{i, j}~ là cạnh nhỏ nhất kề với đỉnh ~j \in R~. Ta dựng linear program ~P_2~ sau:

$$\text{min} \quad\quad\quad \sum_{i \in L} \alpha_i + \sum_{j \in R} \beta_j$$ $$\text{sao cho} \quad\quad\quad \alpha_i + \beta_j \ge p_i + q_j - w_{i, j} \quad \forall (i, j) \in E$$ $$\alpha_i, \beta_j \ge 0$$

—————————

Bổ đề: Sau khi giải ~P_1~ và ~P_2~ tối ưu, ta có $$OPT(P_1) = \sum_{i \in L} p_i + \sum_{j \in R} q_j - OPT(P_2).$$

Chứng minh: Nhận thấy rằng khi ~P_1~ đạt tối ưu, ta luôn có ~0 \le x_i \le p_i~ và ~0 \le y_j \le q_j~ do điều kiện ~x_i + y_j \le w_{i, j}~. Vì thế, với ~\alpha_i = p_i - x_i~ và ~\beta_j = q_j - y_j~, ta luôn có ~\alpha_i, \beta_j \ge 0~; đồng thời, do ~x_i + y_j \le w_{i, j}~, ta có ~\alpha_i + \beta_j = p_i + q_j - (x_i + y_j) \ge p_i + q_j - w_{i, j}~. Vì thế, ~\alpha_i~ và ~\beta_j~ ở đây là một cách assign các biến cho ~P_2~ thoả mãn các điều kiện đã cho, và vì thế ~OPT(P_2) \le \sum_{i \in L} p_i + \sum_{j \in R} q_j - OPT(P_1)~, hay $$OPT(P_1) \le \sum_{i \in L} p_i + \sum_{j \in R} q_j - OPT(P_2).$$

Tiếp theo, nhận thấy rằng khi ~P_2~ đạt tối ưu, ta phải có ~\alpha_i \le p_i~. Giả sử ngược lại, tức ~\alpha_i > p_i~. Với mọi cạnh ~(i, j) \in E~, ta có $$\alpha_i + \beta_j > p_i + 0 \ge p_i + q_j - w_{i, j}$$ do ~q_j \le w_{i, j}~. Vì thế, tất cả các cạnh kề ~i~ đều có điều kiện trên thoả mãn chặt (strictly satisfying). Vì thế, ta có thể giảm ~\alpha_i~ sao cho các cạnh kề ~i~ đều thoả mãn điều kiện ~\alpha_i + \beta_j \ge p_i + q_j - w_{i, j}~, đồng thời làm giảm ~OPT(P_2)~ xuống (ở đây, ta có thể giảm ~\alpha_i~ xuống ~p_i~).

Tương tự, ta có ~\beta_j \le q_j~. Vì thế, nếu gán ~x_i = p_i - \alpha_i~ và ~y_j = q_j - \beta_j~, ta có ~x_i \ge 0~ và ~y_j \ge 0~, và các điều kiện của ~P_1~ được thoả mãn. Vì thế, $$OPT(P_1) \ge \sum_{i \in L} p_i + \sum_{j \in R} q_j - OPT(P_2).$$

Cuối cùng, ta có $$OPT(P_1) = \sum_{i \in L} p_i + \sum_{j \in R} q_j - OPT(P_2).$$

—————————

Vì thế, để giải ~P_1~, ta có thể giải ~P_2~. Tại sao chúng ta lại quan tâm đến ~P_2~? Đặt ~w'_{i, j} = \max(p_i + q_j - w_{i, j}, 0)~, ta có thể biến ~P_2~ thành

$$\text{min} \quad\quad\quad \sum_{i \in L} \alpha_i + \sum_{j \in R} \beta_j$$ $$\text{sao cho} \quad\quad\quad \alpha_i + \beta_j \ge w'_{i, j} \quad \forall (i, j) \in E$$ $$\alpha_i, \beta_j \ge 0$$

Lấy dual của bài toán này, ta thu được ~P_2'~ là

$$\text{max} \quad\quad\quad w'_{i, j} x_{i, j}$$ $$\text{sao cho} \quad\quad\quad \sum_{(i, j) \in E} x_{i, j} \le 1 \quad\quad\quad\ \forall i \in L$$ $$\quad\quad\quad\quad\quad\quad \sum_{(i, j) \in E} x_{i, j} \le 1 \quad\quad\quad\ \forall j \in R$$ $$x_{i, j} \ge 0$$

Đây chính xác là bài cặp ghép có trọng số cực đại: nếu gọi ~x_{i, j}~ là biến biểu diễn có lấy cạnh ~(i, j)~ hay không, thì hai điều kiện đầu tương ứng với việc chọn tối đa một cạnh kề với mỗi đỉnh trái và phải. Để cài đặt, ta có thể dùng Hungarian (với độ phức tạp ~O((mn)^3)~, có thể squeeze qua time limit), hoặc dùng thuật toán min cost max flow (với độ phức tạp ~O((mn)^2 \log(mn))~).

#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;
using namespace atcoder;

const int64_t INF = 1E9 + 7;

void solve() {
    int m, n; cin >> m >> n;
    vector a(m, vector<int>(n));
    int64_t sum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            sum += a[i][j];
        }
    }
    int H = m * n + 1;
    auto zer = [&](int t) { return (t + 1) * H - 1; };
    auto node = [&](int i, int j, int t) {
        if (t == 0) {
            return i == 0 || i == m ? zer(0) : i * n + j;
        } else {
            return j == 0 || j == n ? zer(1) : H + i * n + j;
        }
    };
    vector<int64_t> mi(2 * H, INF);
    vector<vector<pair<int, int64_t>>> adj(2 * H);
    auto add_edge = [&](int u, int v, int64_t w) {
        adj[u].push_back({v, w});
        mi[u] = min(mi[u], w);
        mi[v] = min(mi[v], w);
    };
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int di = 0; di < 2; di++) {
                for (int dj = 0; dj < 2; dj++) {
                    add_edge(node(i + di, j, 0), node(i, j + dj, 1), a[i][j]);
                }
            }
        }
    }
    add_edge(zer(0), zer(1), 0);
    int s = 2 * H, t = 2 * H + 1;
    mcf_graph<int, int64_t> mf(t + 1);
    for (int i = 0; i < 2 * H; i++) {
        if (mi[i] == INF) {
            continue;
        }
        sum -= mi[i];
        if (i < H) {
            mf.add_edge(s, i, 1, 0);
        } else {
            mf.add_edge(i, t, 1, 0);
        }
    }
    for (int u = 0; u < H; u++) {
        for (auto [v, w] : adj[u]) {
            int64_t nw = mi[u] + mi[v] - w;
            mf.add_edge(u, v, 1, INF - max<int64_t>(0, nw));
        }
    }
    auto sl = mf.slope(s, t);
    int64_t bst_cost = 0;
    for (auto [f, c] : sl) {
        bst_cost = max<int64_t>(bst_cost, 1LL * INF * f - c);
    }
    cout << sum + bst_cost << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; cin >> t;
    while (t--) {
        solve();
    }
}