Need Better Approach For Solving This Problem

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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).