등산

세준이는 등산을 좋아한다. 높은 곳에서 도시를 내려다보는 것을 좋아하지만, 겁이 많아서 어두워지기 전에 반드시 호텔로 돌아오려고 한다.

산의 지도는 N행 M열 격자로 주어진다. 각 칸에는 높이를 나타내는 문자 하나가 적혀 있다. 문자 A부터 Z까지는 높이 0부터 25까지를, 문자 a부터 z까지는 높이 26부터 51까지를 뜻한다.

호텔은 좌표 (0, 0)에 있다. 세준이는 현재 칸에서 상하좌우로 인접한 칸으로만 이동할 수 있으며, 두 칸의 높이 차이가 T보다 크면 이동할 수 없다.

낮은 곳이나 같은 높이의 칸으로 이동할 때는 1초가 걸린다. 더 높은 곳으로 이동할 때는 두 칸의 높이 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이 5인 칸에서 높이 9인 칸으로 이동하면 (5 - 9)^2 = 16초가 걸리고, 높이 9인 칸에서 높이 5인 칸으로 이동하면 1초가 걸린다.

산의 지도와 T, 어두워지는 시간 D가 주어졌을 때, 세준이가 호텔에서 출발해 다시 호텔로 돌아오는 데 걸리는 시간이 D 이하가 되도록 갈 수 있는 가장 높은 곳의 높이를 구하라.

첫째 줄에 산의 세로 크기 N, 가로 크기 M, 제한 높이 차이 T, 어두워지는 시간 D가 주어진다.

N과 M은 25 이하의 자연수이다. T는 52 이하의 자연수이고, D는 1,000,000 이하의 자연수이다.

둘째 줄부터 N개의 줄에 산의 지도가 주어진다. 각 줄은 길이가 M인 문자열이다.

세준이가 시간 D 이하로 호텔에서 출발해 다시 호텔로 돌아올 수 있는 경로 중, 도달 가능한 가장 높은 칸의 높이를 첫째 줄에 출력한다.