시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB355881248219.412%

문제

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

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 '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보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 갈 수 있는 가장 높은 곳의 높이를 출력한다.

예제 입력 1

6 6 6 36
AABCDE
GJIHGF
MKLMNO
STSRQP
YUVWXY
edcbaZ

예제 출력 1

30

예제 입력 2

2 2 3 10000
AD
JG

예제 출력 2

9

예제 입력 3

2 2 3 29
AD
JG

예제 출력 3

6

예제 입력 4

7 4 5 14
BCDE
AJKF
AIHG
AAAA
AOMK
AQSI
ACEG

예제 출력 4

10

예제 입력 5

7 4 5 57
BCDE
AJKF
AIHG
AAAA
AOMK
AQSI
ACEG

예제 출력 5

18

예제 입력 6

1 7 3 1000
ABCDEFK

예제 출력 6

5

예제 입력 7

8 9 4 50
TRRVUXefk
bSNMOWcff
bRPNNQZip
XSRUTVcfj
WbZQPXZbV
XdYSRWVOP
feedVVcZR
XhfdZZefg

예제 출력 7

28

출처