// 演算法 / Algorithm:
//   dp[j][c] = 走到目前列、第 j 行,且恰好花成本 c 時的最大分數
//   dp[j][c] = max score upon reaching column j of the current row with exact cost c.
//   逐行 (row-by-row) 滾動更新,讀 dp[j] 拿上一行,讀 dp[j-1] 拿這一行已更新值。
//   We roll row-by-row; dp[j] still holds the previous row, dp[j-1] holds the current row.
//   時間 O(m*n*k),空間 O(n*k) / Time O(m*n*k), space O(n*k).

#include <stdlib.h>  // 提供 malloc / free / provides malloc, free

int maximumPathScore(int** grid, int gridSize, int* gridColSize, int k) {
    int m = gridSize;            // 行數 / number of rows
    int n = gridColSize[0];      // 列數 / number of columns

    // 配置 dp[n][k+1];使用 -1 代表「不可達」/ allocate dp[n][k+1]; -1 means "unreachable"
    int** dp = (int**)malloc(n * sizeof(int*));        // 指標陣列 / array of row pointers
    for (int j = 0; j < n; j++) {                      // 為每一列配置 / allocate each column slice
        dp[j] = (int*)malloc((k + 1) * sizeof(int));   // k+1 個成本桶 / k+1 cost buckets
        for (int c = 0; c <= k; c++) dp[j][c] = -1;    // 初值設為不可達 / mark all unreachable
    }
    dp[0][0] = 0;  // 起點:第 0 列、成本 0、分數 0 / start at column 0, cost 0, score 0

    // 暫存陣列,避免就地寫壞同一行內後面的讀取 / scratch row to avoid clobbering reads
    int* tmp = (int*)malloc((k + 1) * sizeof(int));

    for (int i = 0; i < m; i++) {                      // 由上到下逐行 / iterate rows top-down
        for (int j = 0; j < n; j++) {                  // 由左到右逐列 / iterate columns left-to-right
            if (i == 0 && j == 0) continue;            // 起點已初始化過 / base cell already set
            int v = grid[i][j];                        // 此格的值 0/1/2 / cell value 0, 1, or 2
            int cost = (v != 0) ? 1 : 0;               // 1/2 花費 1,0 不花費 / nonzero cells cost 1
            int score = v;                             // 分數恰好等於 v / score equals the cell value

            for (int c = 0; c <= k; c++) tmp[c] = -1;  // 清空暫存 / clear scratch row

            // c 從 cost 起跳:不到 cost 進不了這格 / start at c=cost: smaller budgets can't enter this cell
            for (int c = cost; c <= k; c++) {
                int prev = c - cost;                   // 進此格前已花的成本 / cost spent before entering
                // 從上面來:dp[j][prev] 還是上一行的值 / "from above" reads previous row at dp[j]
                int from_above = (i > 0 && dp[j][prev] >= 0)
                                    ? dp[j][prev] + score : -1;
                // 從左邊來:dp[j-1][prev] 已是這行更新後的值 / "from left" reads current row at dp[j-1]
                int from_left  = (j > 0 && dp[j-1][prev] >= 0)
                                    ? dp[j-1][prev] + score : -1;
                int best = (from_above > from_left) ? from_above : from_left;  // 取較大 / take the larger
                tmp[c] = best;                          // 寫入暫存 / write into scratch
            }

            for (int c = 0; c <= k; c++) dp[j][c] = tmp[c];  // 把暫存搬回 dp[j] / commit scratch to dp[j]
        }
    }

    int ans = -1;                                      // 預設無解 / default to "no valid path"
    for (int c = 0; c <= k; c++)                       // 在終點掃所有成本 / scan all costs at the goal
        if (dp[n - 1][c] > ans) ans = dp[n - 1][c];    // 取最大分數 / keep the maximum score

    for (int j = 0; j < n; j++) free(dp[j]);           // 釋放每列 / free each column slice
    free(dp);                                          // 釋放指標陣列 / free pointer array
    free(tmp);                                         // 釋放暫存 / free scratch row
    return ans;                                        // 回傳答案;全不可達就是 -1 / return -1 if all unreachable
}