https://usaco.org/index.php?page=viewproblem2&cpid=717〈=ru

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

int n, t;
vector<vector<int>> a;

vector<int> di = {3, -3, 2, 2, -2, -2, 1, 1, -1, -1, 0, 0};
vector<int> dj = {0, 0, 1, -1, 1, -1, 2, -2, 2, -2, 3, -3};

bool in_bounds(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < n;
}

vector<vector<ll>> dijkstra() {
    vector<vector<ll>> dp(n, vector<ll>(n, 1e18));
    dp[0][0] = 0;
    set<array<ll, 3>> st;
    st.insert({0, 0, 0});
    while (!st.empty()) {
        auto p = *st.begin();
        st.erase(st.begin());
        ll d = p[0];
        int i = p[1];
        int j = p[2];
        for (int k = 0; k < 12; k++) {
            int r = i + di[k];
            int c = j + dj[k];
            if (!in_bounds(r, c)) continue;
            ll newd = d + a[r][c] + t*3;
            if (newd < dp[r][c]) {
                st.erase({dp[r][c], r, c});
                dp[r][c] = newd;
                st.insert({dp[r][c], r, c});
            }
        }
    }
    return dp;
}

void solve() {
    cin >> n >> t;
    a.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    auto dp = dijkstra();
    ll ans = dp[n - 1][n - 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int di = n - 1 - i + n - 1 - j;
            if (di < 3) {
                ans = min(ans, dp[i][j] + t * di);
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("visitfj.in", "r", stdin);
    freopen("visitfj.out", "w", stdout);
    solve();
}