Maximum Number of Points with Cost

Hard

You are given an m x n matrix points. You pick exactly one cell in each row. Picking cell (r, c) adds points[r][c] to your score, but for adjacent rows you lose abs(c1 - c2) for the columns picked. Return the maximum score obtainable.

Example 1

Input:  points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9

Example 2

Input:  points = [[1,5],[2,3],[4,2]]
Output: 11

Constraints

• m == points.length
• n == points[i].length
• 1 <= m, n <= 10^5
• 1 <= m*n <= 10^5
• 0 <= points[r][c] <= 10^5.