Code

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

const long long inf = 1e15;

long long solve(vector<vector<int>> &mat, long long c) {
    int row = mat.size(), col = mat[0].size();

    // min_contrib[i][j] represents the minimum contribution of all cells
    // (i', j') such that i' <= i && and j' <= j.
    // Here, contribution is defined as mat[i][j] - c*i - c*j.
    vector<vector<long long>> min_contrib(row, vector<long long>(col, inf));

    long long ans = inf;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            long long prev_min = min(i ? min_contrib[i - 1][j] : inf,
                                     j ? min_contrib[i][j - 1] : inf);
            ans = min(ans, mat[i][j] + c * i + c * j + prev_min);
            min_contrib[i][j] = min(mat[i][j] - c * i - c * j, prev_min);
        }
    }

    // min_contrib[i][j] represents the minimum contribution of all cells
    // (i', j') such that i' <= i && and j' >= j.
    // Here, contribution is defined as mat[i][j] - c*i + c*j.
    for (int i = 0; i < row; i++) {
        for (int j = col - 1; j >= 0; j--) {
            long long prev_min = min(i ? min_contrib[i - 1][j] : inf,
                                     j + 1 < col ? min_contrib[i][j + 1] : inf);
            ans = min(ans, mat[i][j] + c * i - c * j + prev_min);
            min_contrib[i][j] = min(mat[i][j] - c * i + c * j, prev_min);
        }
    }

    return ans;
}

int main() {
    int row, col;
    long long c;
    cin >> row >> col >> c;

    vector<vector<int>> mat(row, vector<int>(col, 0));
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> mat[i][j];
        }
    }

    cout << solve(mat, c) << endl;
    return 0;
}