// 演算法 / Algorithm: 由左往右掃描,維護 dp[h[j-1]][h[j]] = 已完成第 0..j-1 欄貢獻的最大分數。
// 轉移時枚舉下一欄高度 c,把第 j 欄延後的貢獻 S(j, h[j], max(h[j-1], c)) 加進去。
// Sweep columns left-to-right; dp[a][b] = best score with h[j-1]=a, h[j]=b and columns 0..j-1
// fully booked. Each transition picks h[j+1]=c and adds column j's deferred contribution.

#include <stdlib.h>     // 提供基本型態 / basic types
#include <string.h>     // 提供 memcpy / for memcpy
#include <limits.h>     // 提供 LLONG_MIN / for LLONG_MIN

long long maximumScore(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize;                                   // n 為網格邊長 / n is the grid side length

    // static 讓陣列在 BSS 區,避免爆掉函式呼叫堆疊 / static keeps arrays off the call stack
    static long long colSum[101][102];                  // colSum[j][k]=第 j 欄前 k 列之和 / column-j prefix sum
    static long long dp[102][102], ndp[102][102];       // 滾動兩層 / rolling DP layers
    const long long NEG = LLONG_MIN / 4;                // 標記不可達狀態,除以 4 避免相加溢位 / sentinel for unreachable, /4 avoids overflow when added

    // 預計算每欄的前綴和,讓任意列區間和能 O(1) 取得 / precompute per-column prefix sums for O(1) range queries
    for (int j = 0; j < n; j++) {                       // 對每一欄 / for each column
        colSum[j][0] = 0;                               // 空前綴和為 0 / empty prefix sums to 0
        for (int i = 0; i < n; i++) {                   // 從上到下累加 / accumulate top-down
            // 強制轉成 long long,避免在 int 範圍相加時溢位 / cast to long long to avoid int overflow
            colSum[j][i + 1] = colSum[j][i] + (long long)grid[i][j];
        }
    }

    // 初始化 j=0 的狀態 / initialize states for column j=0
    for (int a = 0; a <= n; a++)                        // a = h[-1] (虛擬左鄰) / a = h[-1] (virtual left neighbor)
        for (int b = 0; b <= n; b++)                    // b = h[0]
            dp[a][b] = NEG;                             // 預設不可達 / default unreachable
    for (int b = 0; b <= n; b++)                        // 規定 h[-1]=0,所以只有 a=0 合法 / convention h[-1]=0, only a=0 is valid
        dp[0][b] = 0;                                   // 還沒加任何貢獻 / no contributions added yet

    // 主迴圈:由 j 轉移到 j+1 / main loop: transition from column j to column j+1
    for (int j = 0; j + 1 < n; j++) {
        // 重置 ndp / reset ndp
        for (int b = 0; b <= n; b++)
            for (int c = 0; c <= n; c++)
                ndp[b][c] = NEG;

        for (int b = 0; b <= n; b++) {                  // b = h[j] = 上一狀態的 b / b is current column's height
            for (int c = 0; c <= n; c++) {              // c = h[j+1] = 想決定的下一欄高度 / c is next column's height
                long long best = NEG;                   // 在所有 a 中取最大 / take max over all a
                for (int a = 0; a <= n; a++) {          // a = h[j-1] = 上一狀態的 a / a is previous-previous column's height
                    if (dp[a][b] <= NEG) continue;      // 跳過不可達狀態 / skip unreachable
                    int top = (a > c) ? a : c;          // top = max(h[j-1], h[j+1]) 決定第 j 欄白色貢獻邊界 / top sets the upper bound for column j's white contributions
                    // 第 j 欄的貢獻:第 b 列到第 top-1 列的數值和,若 b ≥ top 則為 0
                    // Column j's contribution: sum of rows [b, top); if b ≥ top, no white cell qualifies
                    long long contrib = (b < top) ? (colSum[j][top] - colSum[j][b]) : 0;
                    long long val = dp[a][b] + contrib; // 加上延後的貢獻 / add deferred contribution
                    if (val > best) best = val;         // 更新最大值 / update max
                }
                ndp[b][c] = best;                       // 寫入新狀態 / store new state
            }
        }
        memcpy(dp, ndp, sizeof(dp));                    // 滾動:把 ndp 變成下一輪的 dp / roll layers: ndp becomes dp
    }

    // 最後一欄(j = n-1)還欠一次貢獻,用 h[n]=0 套公式 / last column still has a deferred contribution; apply with h[n]=0
    long long ans = 0;                                  // 答案至少為 0(全不操作) / answer is at least 0 (no operations)
    int j = n - 1;
    for (int a = 0; a <= n; a++) {
        for (int b = 0; b <= n; b++) {
            if (dp[a][b] <= NEG) continue;              // 不可達跳過 / skip unreachable
            // h[n]=0,top = max(a, 0) = a,故貢獻為 [b, a) 之和
            // h[n]=0 makes top = a, so contribution is sum over rows [b, a)
            long long contrib = (b < a) ? (colSum[j][a] - colSum[j][b]) : 0;
            long long val = dp[a][b] + contrib;
            if (val > ans) ans = val;                   // 取最大 / track max
        }
    }
    return ans;                                         // 回傳最大分數 / return the max score
}