50 - ZOJ Monthly, February 2006 - 1002
In a campaign, a tank was badly damaged by the enemy. The tank was on fire and was going to explode in a few minutes. But the brave tankman decided he would never surrender but fight with the enemy to the last minute!
Now let us consider this situation: the tank is at the southwest point of the map at the beginning and was going to explode in T minutes. As the tank was badly damaged, it could just go in the north or east direction(the driving system was damaged). But the tank still had the ability to attack and had an attack range of R units, i.e. the tank could attack any target of index (X,Y) subjected to -R<=X,Y<=R relative to it, but of course not itself. During each minute, the tank could move one unit to the north or to the east, or stay in the same position and attack one enemy structure with a marked value(the enemy structure will be immediately destroyed), or do nothing. Notice that the tank could not move through or over the enemy structure, even if the enemy structure was all ready destroyed.
Now we want to know: before the tank exploded, what is the maximum value could be obtained by attacking the enemy structures.
This problem contains multiple test cases! In the first line of each test case, there is an interger T(0<T<=100), the time before the tank would explode(i.e. the tank will explode in minute T+1). The second line contains two integers: N and M (1<N, M<=100), which are the numbers of rows and columns of the map, respectively. The next N rows each have M non-negative integers separated by one space, discribing the map. If the number Aij in row i column j is 0, there is nothing on the ground. Otherwise there is an enemy structure with value Aij.Then the next line there is an integer R(0<R<=10) describing the attack range of the tank. There is a blank line between each input test case.(For clarification, you can refer to the sample data and the corresponding figures)
For test case, output one line containing one integer, the maximum value will be obtained.Sample Input:
8 5 5 0 0 0 0 20 0 2 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 1 9 5 5 0 0 0 0 20 0 2 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 1Sample Output: