Need Better Approach For Solving This Problem

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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