Need Better Approach For Solving This Problem

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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