
ZOJ Problem Set  3268
Description Facer is addicted to a game called "Tidy is learning to swim". But he finds it too easy. So he develops a new game called "Facer is learning to swim" which is more difficult and more interesting. In the new game, a robot named "Facer" is swimming in a pool. The pool can be considered as a vertical N*M grid. The coordinates of the topleft cell is (1,1), and the coordinates of the bottomright cell is (N,M). Cells in the top rows are called "surface cells", and all other cells are called "under water cells".
Facer starts swimming from the topleft cell (1,1) and must arrive at the topright cell (1,M). He has a constant horizontal speed of 1 per second, and a vertical speed of v per second. v is always integer and can be changed. If v is positive, it means Facer is moving down; and if v is negative, it means Facer is moving up. So if Facer is at cell (x,y) now , he will arrive at cell (x+v,y+1) after a second. Be careful that if x+v>N, Facer will get to cell (N,y+1) because he cannot move down anymore and of course if x+v<1, Facer will get to cell (1,y+1) because he cannot fly. Please remember that all the "under water cells" in the rightmost column are poisonous. If Facer goes into those cells, he will die. The capacity of Facer's oxygen bottle is limited, and when Facer gets into a surface cell, the oxygen bottle is refilled automatically. Facer has to refill his oxygen bottle every K seconds, which means that during the time between two refillings, Facer can only pass at most K1 under water cells in the horizontal direction. In every cell, there is either a "speed changing machine" or a "money box" (can't be both). Every speed changing machine has a value T and every money box has a value P. You have got enough number of devices called "speedo". Every speedo has a value Q which is 1 or 1. You can put your speedos in any cells, but you can put at most one speedo in a cell. When Facer reaches a cell, the speed changing machine of value T in that cell (if there is one) will change his vertical speed by T, and the speedo of value Q in that cell (if there is one) will change his vertical speed by Q. For example, if Facer's vertical speed is v when he arrives at a cell with a speed changing machine of value T and a speedo of value Q, his vertical speed will be changed to v + T + Q immediately. There are three more things you need to know about speed changing:
When arriving at a cell with a money box of value P, Facer gets P dollars (In fact, if P is negative, Facer loses P dollars). Facer's total amount of money can be negative  that means Facer owes some money to the pool's owner. You task is deploying your speedos in a smart way before Facer starts swimming, so Facer can get money as much as possible when he arrives at cell (1,M). Facer's initial vertical speed is zero and if you put a speedo in the cell (1,1), it will change Facer's initial vertical speed. Input Multiple test cases, ended by a line of "0 0 0". For each test case: The first line contains three integers N,M and K (1<=N<=100, 1<=M<=1000, 1<=K<=10), tells the size of the pool and Facer must refill the oxygen bottle every K seconds. Following are N lines describing the cells by top to bottom order. Each line contains M elements, separated by blanks, telling the information about the cells of a row, by left to right order. There are only two kinds of elements:
Output For each test case, output one line containing an integer representing the maximum amount of money Facer can get when he reaches cell (1,M). Sample Input 5 10 3 $81 $47 $3 $0 $82 $31 $89 v0 $97 v1 $14 $94 v1 v1 v1 $106 v1 v0 v1 v0 $93 $105 v1 $219 v0 v0 v1 v1 $225 v1 v0 $160 v1 v1 $348 $120 $240 $392 $280 $172 $305 $455 $140 v1 $455 v0 v1 v0 v1 $410 0 0 0 Sample Output 430 Source: Asia 2009, Ningbo (Mainland China) 