#1597 HillWalker

28  10 s   128 MB  

Description

John is currently on a hillwalking holiday in a mountainous region. He really enjoys getting to high altitudes to enjoy the spectacular views of the region and he is planning a walk today that will get him to as high an altitude as possible. However, he also wants to be back at his hotel before it starts to get dark.
You are given a map of the region as a two-dimensional array of characters L, describing a rectangluar section of the landscape. The altitude of the landscape at coordinates (j, i) is an integer represented by character j in element i of L, which will either be an uppercase letter ('A'-'Z') representing altitudes from 0 to 25, respectively, or a lowercase letter ('a'-'z'), representing altitudes from 26 to 51, respectively. John starts off at his hotel at coordinates (0, 0) and is planning to walk between points with integer coordinates. In each segment of his walk, he can walk to any orthogonally adjacent point, as long as the magnitude of the difference in altitude is no greater than K, otherwise the path is too steep. He cannot walk on a path that is too steep, regardless of whether he is walking uphill or downhill. If he walks from some point to another that is at equal or lower altitude (i.e., walking level or downhill) then the time it takes to walk between the points is 1. If he walks to a point at higher altitude (i.e., uphill) then the amount of time it takes is given by the difference in altitude between the points squared. For example, if he were to walk from a point with altitude 5 to one with altitude 9, then it would take (9 - 5) ^ 2 = 16 time units to walk that segment. If he were to walk the same segment, but in the opposite direction, it would only take him a single time unit.
Find the altitude of the highest point that he can reach on any walk that starts and finishes at (0, 0), given that the total time taken for the walk may not be greater than D.

Input

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of rows of L, R (1 <= R <= 25), the number of columns of L, C (1 <= C <= 25), the threshold K (1 <= K <= 52), the time limit D (1 <= D <= 1,000,000).
Next R line gives C characters consisting each rows of L.

Output

For each test case, output the altitude of the highest point on each line.

Sample Input

Sample Output

3
2 2 3 10000
AD
JG
2 2 3 29
AD
JG
6 6 6 36
AABCDE
GJIHGF
MKLMNO
STSRQP
YUVWXY
edcbaZ
9
6
30