All submissions for this problem are available.You are given a $M\times N$ grid and on each cell there is a coin. A coin may have integral value denoted by $C[i][j]$. If you're at a cell $(i,j)$, then you have to pick up the coin present at that cell(whose value is $C[i][j]$) and you can visit a cell $only$ $once$ . You are initially at $(1,1)$ and you have to reach $(M,N)$. Note that you can only move $right$, $up$ or $bottom$ from a given cell. Formally, if you are at position $(i,j)$ ,then you can move to $(i+1,j)$, $(i-1,j)$ or $(i,j+1)$. Following the conditions given above, what is the total $maximum$ value of coins you can have after reaching $(M,N)$? ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase contains of a single line of input, two integers $M, N$. - Each of the next $M$ lines consist of $N$ integers, the values of coins denoted by $C[i][j]$ . ###Output: For each testcase, output in a single line the total maximum value of coins you can have after reaching $(M,N)$. ###Constraints - $1 \leq T \leq 20$ - $1 \leq M, N \leq 1000$ - $-10^9 \leq C[i][j] \leq 10^9$ ###Subtasks - 20 points : All coins have $equal$ and $positive$ value. - 80 points : Original Constraints. ###Sample Input: 1 3 3 1 -2 3 2 4 3 -10 2 7 ###Sample Output: 18 ###EXPLANATION: Best Possible path is $ ->  ->  -> [-2] ->  ->  -> $ ,giving a total value of 18.
|Tags||dynamic-programming, easy-medium, ratik_21|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions