시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 986 260 175 31.028%

문제

아래와 같이 M행 N열 격자 그리드로 설계된 운전 면허 시험장에서 운전 면허 시험을 치르려 한다.

시험의 규칙은 세 가지이다.

  • 규칙 1 : 응시자는 가장 왼쪽 위의 s지점에서 시작하여 동쪽(오른쪽), 남쪽(아래쪽)으로만 차를 몰아 가장 오른쪽 아래의 최종 도착지 t에 도착해야 한다.
  • 규칙 2 : 차를 아래로 모는 시간과 오른쪽으로 모는 시간은 격자 한 칸당 L로 동일해야 한다. (L은 시험 시작 전에 주어지는 상수이다). 또한, 방향을 바꾸는 데 걸리는 시간은 항상 1이다. 단, 시작점 s에서는 오른쪽이나 아래 방향 중 원하는 방향을 골라 출발할 수 있다. 즉, 시작점에서는 방향을 바꾸는 데 시간이 들지 않는다.
  • 규칙 3 : 시험을 시작하기 전 G만큼의 연료를 주입한다.(G는 시험 시작 전에 결정된다). 응시자는 G 이하의 연료를 사용한다는 조건 하에 가장 빨리 도착할 수 있는 방법으로 t에 도착해야 한다.

규칙 2를 만족하기 위해, 응시자는 도로의 상태에 따라 알맞은 방법으로 차를 몰아야 한다. 따라서, 각 도로의 상태에 따라 소모되는 연료량이 다르다. 이에 따라 응시자는 G 이하의 연료만을 사용하여 t에 도착하는 경로를 찾아야 한다.

위에 예시로 주어진 4*6 그리드에서 각 도로에 쓰여진 정수가 그 도로를 시간 L동안 주행하는 데에 드는 연료량이다. 방향을 바꿀 때는 연료가 사용되지 않는다.

위의 그림은 G=19이며 L=10일 때 가능한 두 가지 경로를 표시한 것이다.

왼쪽의 경로는 17의 연료를 사용하여 83의 시간만에 아래에 도달하는 경로이다. 이 경로에는 8번의 직선 주행과 3번의 방향 변경이 있었다. 오른쪽의 경로는 연료를 덜 쓰는 경로이지만(16), 주행 시간의 합이 85로 더 오래 걸린다. 사실 위의 경로 외에도 19 이하의 연료 사용으로 83의 시간으로 도달할 수 있는 경로가 몇 가지 더 있다. 하지만, 19 이하의 연료를 사용하여 83보다 더 빠른 시간 내에 t에 도착하는 방법은 존재하지 않는다.

이제 주행 시험이 시작된다. 그리드의 상태와 G, L이 주어질 때, 가장 빠르게 목적지 t에 도달하는 시간은 얼마일까?

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 네 개의 정수 M, N, L, G로 이루어져 있으며 M은 그리드의 행 수, N은 그리드의 열 수이다. L은 문제에서 설명한 한 격자를 직선 주행하는 데 걸리는 시간이며 G는 연료량이다. (2 ≤ M, N ≤ 100), (1 ≤ L ≤ 10), (1 ≤ G ≤ 1,000,000). 이어서 M줄에 걸쳐 N-1개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 가로 경로를 주행할 때 드는 연료량이다. 그 이후 M-1줄에 걸쳐 N개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 세로 경로를 주행할 때 드는 연료량이다.

모든 단위 경로에서 소모되는 연료량은 1 이상 1000 이하의 값을 갖는다.

출력

만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다.

예제 입력

3
4 6 10 19
4 3 6 7 9
3 1 2 7 5
2 2 6 1 9
5 3 4 3 2
1 5 4 4 4 2
6 1 1 3 1 7
2 2 3 2 3 5
3 4 5 10
4 5 6
2 3 1
5 7 8
1 8 6 7
4 6 9 1
3 3 10 9
2 2
2 2
2 2
3 3 3
3 3 3

예제 출력

83
27
-1

힌트