Jewel Magnetizer

The block world is divided into n rows n columns of blocks. Rows are numbered 1 to n from top to bottom, and columns are numbered 1 to n from left to right. You start from a square, follow a strictly height-decreasing path until no legal moves are possible. During your trip, you can use a jewel magnetizer to get jewels not too far away. To be precise, you can get a jewel in square (r1,c1) if and only if there is a square (r2, c2) on your path such that max {|r1 − r2|, |c1 − c2|} ≤ r. There is one thing you should be aware of: your bag capacity is limited, so you can only get at most m jewels. There is at most one jewel on each block. (a) height (b) jewel value The picture above shows an example. The numbers in the left picture describes the heights in each block, where the numbers in the right picture describes the jewel values in each block. An optimal solution for m = 5 and r = 1 is shown in the figures. The arrows denote the path, gray squares corresponds to jewels you should get. The total value is 4+3+2+2+1=12. Write a program to get the highest total value of jewels. Input The input consists of at most 30 test cases. Each case begins with a line containing three non-negative integers n, m and r (1 < n < 21,0 < m < 101,r < 6), where n is the size of the block world, m is the bag capacity, r is the range of jewel magnetizer. The second line contains two integers r0, c0 (1 ≤ r0,c0 ≤ n), the row number and column number of the initial position. The next n lines each contain n non-negative integers not greater than 8000, the heights of each block. The next n lines each contain n non-negative integers not greater than 1000, the value of jewel at each block (zero means there is no jewel). The last case is followed by a single zero, which should not be processed. Output For each test case, print the case number and the highest value. Sample Input 551 33 11111 16951

2/2 1 3 10 3 1 12121 11111 41112 11111 12312 12111 11111 421 13 4569 3999 2119 9999 0001 0000 0000 0015 0 Sample Output Case 1: 12 Case 2: 2