// 演算法 / Algorithm: 同 C 版本 — 由左往右 DP,dp[a][b] 表示已完成 0..j-1 欄貢獻、且 h[j-1]=a、h[j]=b 的最大分數。
// Same as the C version: left-to-right DP where dp[a][b] is the best score with columns 0..j-1
// fully booked, h[j-1]=a, h[j]=b. Transitions choose h[j+1]=c and pay column j's deferred contribution.

#include <vector>       // std::vector 動態陣列 / std::vector dynamic array
#include <climits>      // LLONG_MIN
#include <algorithm>    // std::max
using namespace std;

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();                                   // n = 邊長 / n = side length

        // 每欄前綴和:colSum[j][k] = grid[0..k-1][j] 之和 / per-column prefix sum
        // vector<vector<long long>> 為二維動態陣列,用 long long 避免 overflow
        // 2D dynamic array of long long to prevent overflow
        vector<vector<long long>> colSum(n, vector<long long>(n + 1, 0));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];  // 自動提升為 long long / auto-promotes to long long
            }
        }

        const long long NEG = LLONG_MIN / 4;                   // 不可達狀態哨兵 / unreachable sentinel
        // dp[a][b]:目前欄為 j,a = h[j-1],b = h[j] / dp[a][b]: a is h[j-1], b is h[j] for current j
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, NEG));
        for (int b = 0; b <= n; b++) dp[0][b] = 0;             // 初始 j=0:只有 a=0 合法 / init j=0: only a=0 valid

        // 一欄欄推進 / advance column by column
        for (int j = 0; j + 1 < n; j++) {
            // 新一層的 dp,先全填 NEG / fresh layer, default NEG
            vector<vector<long long>> ndp(n + 1, vector<long long>(n + 1, NEG));
            for (int b = 0; b <= n; b++) {                     // b = h[j]
                for (int c = 0; c <= n; c++) {                 // c = h[j+1]
                    long long best = NEG;
                    for (int a = 0; a <= n; a++) {             // a = h[j-1]
                        if (dp[a][b] <= NEG) continue;         // 不可達 / unreachable
                        int top = max(a, c);                   // 第 j 欄白色貢獻的上邊界 / upper bound of column j's white contribution
                        // 用前綴和 O(1) 算第 j 欄列 [b, top) 之和 / O(1) range sum of column j rows [b, top)
                        long long contrib = (b < top) ? (colSum[j][top] - colSum[j][b]) : 0;
                        best = max(best, dp[a][b] + contrib);  // 取最佳 / keep the best
                    }
                    ndp[b][c] = best;
                }
            }
            dp = move(ndp);                                    // 滾動,move 避免複製成本 / roll layers; move avoids deep copy
        }

        // 最後加上 j=n-1 欄的延後貢獻,假設右邊高度為 0 / pay column n-1's deferred contribution with h[n]=0
        long long ans = 0;
        int j = n - 1;
        for (int a = 0; a <= n; a++) {
            for (int b = 0; b <= n; b++) {
                if (dp[a][b] <= NEG) continue;
                // h[n]=0,故 top = max(a, 0) = a,貢獻為列 [b, a) 之和
                // h[n]=0 → top = a, contribution = sum over rows [b, a)
                long long contrib = (b < a) ? (colSum[j][a] - colSum[j][b]) : 0;
                ans = max(ans, dp[a][b] + contrib);            // std::max 比較取大者 / std::max picks the larger
            }
        }
        return ans;                                            // 最終答案 / final answer
    }
};