class Solution {
    int res = 0;
    public long maxPoints(int[][] points) {
        dfs(points,0,0,0);
        return res;
    }
    public void dfs(int[][] points,int row, int col, int score){
        if (row >= points.length) {
            res = Math.max(res,score);
            return;
        }
        for (int i = 0; i < points[row].length; i++) {
            int newScore = score + points[row][i];
            if (row > 0){
                newScore -= Math.abs(col - i);
            }
            dfs(points,row+1,i,newScore);
        }
    }
}

class Solution {
    public long maxPoints(int[][] points) {

        if (points.length == 0) {
            return 0;
        }
        long result = 0;
        int m = points.length;
        int n = points[0].length;
        long[][] dp = new long[m][n];
        for (int i = 0; i < n; i++) {
                dp[0][i] = points[0][i];
            result = Math.max(result,dp[0][i]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    long score = points[i][j] + dp[i-1][k] - Math.abs(j-k);
                    dp[i][j] = Math.max(score,dp[i][j]);
                }
                result = Math.max(result,dp[i][j]);
            }

        }
        return result;

    }
    
}