AMR11A  Magic Grid
Thanks a lot for helping Harry Potter in finding the Sorcerer's Stone of Immortality in October. Did we not tell you that it was just an online game ? uhhh! now here is the real onsite task for Harry. You are given a magrid S ( a magic grid ) having R rows and C columns. Each cell in this magrid has either a Hungarian horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at a cell (i,j) takes away S[i][j] strength points from him, and a potion at a cell (i,j) increases Harry's strength by S[i][j]. If his strength drops to 0 or less at any point during his journey, Harry dies, and no magical stone can revive him.
Harry starts from the topleft corner cell (1,1) and the Sorcerer's Stone is in the bottomright corner cell (R,C). From a cell (i,j), Harry can only move either one cell down or right i.e., to cell (i+1,j) or cell (i,j+1) and he can not move outside the magrid. Harry has used magic before starting his journey to determine which cell contains what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to start with to collect the Sorcerer's Stone. Please help him once again.
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of R C in the first line followed by the description of the grid in R lines, each containing C integers. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with S[i][j] < 0 contain dragons, others contain magic potions.
Output (STDOUT):
Output T lines, one for each case containing the minimum strength Harry should start with from the cell (1,1) to have a positive strength through out his journey to the cell (R,C).
Constraints:
1 ≤ T ≤ 5
2 ≤ R, C ≤ 500
10^3 ≤ S[i][j] ≤ 10^3
S[1][1] = S[R][C] = 0
Sample Input:
3
2 3
0 1 3
1 2 0
2 2
0 1
2 0
3 4
0 2 3 1
1 4 0 2
1 2 3 0
Sample Output:
2
1
2
Explanation:
Case 1 : If Harry starts with strength = 1 at cell (1,1), he cannot maintain a positive strength in any possible path. He needs at least strength = 2 initially.
Case 2 : Note that to start from (1,1) he needs at least strength = 1.
hide comments
SUBHAM SANGHAI:
20160525 09:43:07
nice qstn.. DP+Binary Search 

Sushovan Sen:
20160409 12:44:52
@Sarvesh : case :


sarvesh_19:
20160222 11:50:37
http://ideone.com/ldccsz showing wrong answer here and all spoj toolkit test cases giving right answer .Please Help:( 

minhthai:
20160215 17:08:38
not as simple as it seems :) 

naruto09:
20151214 22:34:58
getting WA..any tricky test case please..? 

spoj2121:
20151031 19:51:44
amazing question....not at easy as it looks... 

dark_lord1:
20150818 10:22:58
Its not as easy as it looks..nice question..Makes me think what is recursion all about and what to return after from every recursive call..Must try...O(rows*columns) will work :) 

detel:
20150722 11:28:59
It's not as easy as I thought!!! 

^_^:
20150618 00:02:35
unable to find error in my code can someone please provide some tricky testcase. 

i_am_looser:
20150608 22:08:56
@!(loGic) constraints clearly says 2<=R,C<=500 
Added by:  Varun Jalan 
Date:  20111215 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Anil Kishore  ICPC Asia regionals, Amritapuri 2011 