값싼 기름

당신은 매일 도시를 가로질러 직장으로 운전해 갑니다. 요즘 기름값이 매우 비싸졌습니다. 그런데 기름값이 도시 안에서도 장소마다 다르다는 것을 알게 되었습니다. 가장 싼 주유소가 도시 반대편에 있을 때도 있는데, 단지 싸게 주유하려고 그 먼 곳까지 운전해 갈 가치가 있는지 궁금합니다. 기름값으로 쓰는 돈은 최대한 줄이고 싶지만, 연료 탱크의 용량이 한정되어 있으므로 도중에 연료가 바닥나서는 안 됩니다. 그래서 매일 사무실에 도착하기 위해 써야 하는 최소 금액을 계산하고 싶습니다.

다행히 당신은 격자 도시에 살고 일합니다. 이 도시에서는 도로(street)가 동서로 뻗어 있고, 대로(avenue)가 남북으로 뻗어 있습니다. 도로에는 $1$번부터 차례로 번호가 매겨져 있고, 대로에도 $1$번부터 차례로 번호가 매겨져 있습니다. 시민들은 자신의 위치를 도로 번호와 대로 번호의 쌍으로 나타냅니다. 예를 들어 $(3,2)$는 3번 도로와 2번 대로가 만나는 교차로를 뜻합니다.

수년간의 "실전 실험" 끝에, 당신은 이 도시에 관한 놀라운 사실을 알아냈습니다. 어떤 교차로에서 인접한 교차로(북, 동, 남, 서 중 한 방향으로 한 블록)로 이동하는 데에는 언제나 정확히 1리터의 연료가 듭니다. 사무실이나 주유소에 연료가 $0$리터 남은 상태로 도착해도 괜찮습니다.

주유소가 있는 교차로에서는 원하는 만큼 많이 또는 적게 주유할 수 있습니다. 다만 탱크 용량을 넘겨서 넣으면 초과분은 낭비되므로, 용량을 초과해 주유할 수는 없습니다.

입력의 첫 줄에는 테스트 케이스의 개수 $t$가 주어집니다.

각 테스트 케이스의 첫 줄에는 네 정수 $m$, $n$, $f$, $k$가 주어집니다. $m$은 도로의 수, $n$은 대로의 수이며 $(1 \le m,n \le 100)$입니다. $f$는 연료 탱크의 최대 용량(리터)입니다. 출발 위치는 $(1,1)$이고 사무실은 $(m,n)$에 있으며, 당신은 $(1,1)$에서 가득 찬 탱크로 출발합니다.

이어지는 $k$개의 줄에는 각각 세 수 $a$, $b$, $c$가 주어집니다. $a$와 $b$는 정수이고 $(a,b)$는 주유소의 위치이며, $c$는 그 주유소의 기름값입니다.

각 테스트 케이스마다 기름값으로 써야 하는 최소 금액을, 가장 가까운 센트 단위로 반올림하여 소수점 아래 두 자리까지 출력합니다. 연료가 바닥나지 않고 사무실에 도착하는 것이 불가능하다면, 대신 Stranded on the shoulder를 출력합니다.