Robot Game

All submissions for this problem are available.
Robot Game
There is a maze of size N*M, consisting of unit blocks. At the start Robot has RC percentage of battery charged.
Now Robot start from 1 st row and move towards N th row. From the present block robot can move to a block in the next row, which is either on right or on left side of the present block. On moving to a block in i th row j th column, Robots battery charge will reduce by C(i,j) percent if C(i,j) is greater then 0, else it will be recharged by C(i,j) percent.
For Example if battery has 50 percent of charge, on moving to block with C(i,j) = 15, battery will have 35 ( 50 15 ) percent of the charge.
Now the task is to find out the status of the battery in the end, if the Robot moves optimally to save maximum charge. ( Remember : Battery Charge will not exceed more than 100 percent, and Robot will not move further if Battery charge goes down to 0 percent ).
Input
First line of the input contains T, number of test cases.
In Each test case
First line consists of three space separated integers N, M and RC, representing values as described in the question.
Next N line contains M space separated Integers,( starting from 1 st row ). j th Integer in i th row is
C(i,j), charged gained or reduced on moving to i th row j th column in the maze.
Output
For each test case print a single line containing single integer FC, maximum possible percentage of charge in the battery when Robot reaches N th row. If Robot can not reach the N th row then print 1.
Constraints
 1 <= T <= 10
 1 <= N,M <= 500
 0 <= RC <= 100
 100 <= C(i,j) <= 100
Sample Input
1 4 4 50 10 10 10 10 10 10 10 10 5 5 5 5 5 5 5 5Sample Output
80
Explanation
 One of the optimal move will be <1,2> > <2,1> > <3,2> > <4,1>, in this move Robot gains 30 percent of the charge hence in the end Battery will have 80 percent of charge
Author:  hkbharath 
Tags  hkbharath 
Date Added:  19022014 
Time Limit:  0.190217  0.380435 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, CAML, ICK, BF, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 