以下の事実が重要です。

• 移動の過程でマス \((i,j)\) を訪れる場合、マス \((i,j)\) でコインを回収しご飯を買うのは、移動経路によらず常に \(i+j-1\) 日目である。

証明は、\(1\) 回の移動のたびに \(i+j\) の値がちょうど \(1\) だけ増加することから従います。

よって、\(B_{i,j}=A_{i,j}-P_{i+j-1}\) と定義すると、以下のように問題を言い換えることができます。

• マス \((i,j)\) を訪れると \(B_{i,j}\) 円を得る（\(B_{i,j}<0\) の場合、\(-B_{i,j}\) 円を失う）。右または下への移動を繰り返すことで、所持金が負になることなく \((1,1)\) から \((N,N)\) まで移動したいとき、最初に何円以上持っている必要があるか？

以下のように DP を定義します。

• \(\mathrm{dp}_{i,j}:\) スタート地点がマス \((i,j)\) で、所持金が負になることなく \((H,W)\) まで移動したいとき、最初の所持金（マス \((i,j)\) で \(B_{i,j}\) 円を得る前の所持金）として必要な金額の最小値

この DP は \(i,j\) の降順に求めていくことができます。具体的な遷移は以下の通りです：

• \(\mathrm{dp}_{H,W}=\max\{0,-B_{H,W}\}\)
• \(\mathrm{dp}_{i,j}= \max\{0,\min\{\mathrm{dp}_{i+1,j},\mathrm{dp}_{i,j+1}\}-B_{i,j}\}\quad((i,j) \neq (H,W))\)

ただし便宜上、\(i>H\) または \(j>W\) のとき \(\mathrm{dp}_{i,j}=\infty\) と定義します。

計算量は \(O(HW)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> p(h + w - 1);
    for (int &i: p) cin >> i;
    vector dp(h, vector<ll>(w, 1e18));
    dp[h - 1][w - 1] = 0;
    for (int i = h - 1; i >= 0; i--) {
        for (int j = w - 1; j >= 0; j--) {
            if (i + 1 < h) dp[i][j] = min(dp[i][j], dp[i + 1][j]);
            if (j + 1 < w) dp[i][j] = min(dp[i][j], dp[i][j + 1]);
            dp[i][j] += p[i + j] - a[i][j];
            dp[i][j] = max(dp[i][j], 0LL);
        }
    }
    cout << dp[0][0] << endl;
}