Mountain Climbing

Sejun likes mountain climbing. He enjoys looking down at the city from high places, but because he is timid, he must return to his hotel before it gets dark.

The mountain map is given as an N by M grid. Each cell contains one character representing its height. Characters from A to Z represent heights 0 through 25, and characters from a to z represent heights 26 through 51.

The hotel is at coordinate (0, 0). From the current cell, Sejun may move only to one of the four adjacent cells. If the height difference between the two cells is greater than T, he cannot move there.

Moving to a lower cell or a cell of the same height takes 1 second. Moving to a higher cell takes the square of the height difference in seconds. For example, moving from height 5 to height 9 takes (5 - 9)^2 = 16 seconds, while moving from height 9 to height 5 takes 1 second.

Given the mountain map, T, and the time D until darkness, find the maximum height Sejun can reach while starting from the hotel and returning to the hotel within at most D seconds.

The first line contains the mountain height N, width M, allowed height difference T, and time limit D.

N and M are positive integers not greater than 25. T is a positive integer not greater than 52, and D is a positive integer not greater than 1,000,000.

The next N lines contain the mountain map. Each line is a string of length M.

Print, on the first line, the greatest height of any cell Sejun can reach on a route that starts at the hotel and returns to the hotel within time D.