Problem Statement

A matrix consist of N rows and M column. Select exactly one element from each row such that sum of selected element is maximum possible and sum of column number from which these elements are selected is less than or equal to M. Output this maximum possible sum. Assume 0 based indexing. All elements in matrix is non negative integer less than 10^9.

Example

if N = 3 and M = 3, and matrix is 1 2 3 3 1 4 3 2 1 then output is 9. as we can select elements at (0, 1), (1, 2), (3, 0). sum of column number here is 1 + 2 + 0 = 3

My Approach

I tried to solve it in bottom up manner. I make a dp[n][m] where dp[i][j] represent maximum sum till ith row where sum of column number is j.but it takes me O(M) time to fill each cell in dp as i calculate sum for all possible ways to reach at that state and then select optimal.Thus overall complexity reach to O(N * N * M).

What i want?

I think there should be an approach that can solve this problem in less than O(N * M * M) complexity ? Please suggest any better approach