운전 면허 시험

$M$행 $N$열 격자로 만든 시험장에서 운전 면허 시험을 치른다.

시험 규칙은 세 가지다.

• 규칙 1: 응시자는 가장 왼쪽 위 지점 s에서 출발해 동쪽(오른쪽)과 남쪽(아래쪽)으로만 차를 몰아 가장 오른쪽 아래 지점 t에 도착해야 한다.
• 규칙 2: 격자 한 칸을 직선으로 지나는 시간은 오른쪽이든 아래쪽이든 $L$로 같다. $L$은 시험 전에 주어지는 상수다. 방향을 바꾸는 데 걸리는 시간은 항상 1이다. 다만 출발점 s에서는 오른쪽과 아래쪽 중 원하는 방향을 골라 출발할 수 있고, 이때는 방향을 바꾸는 시간이 들지 않는다.
• 규칙 3: 시험 전에 연료를 $G$만큼 넣는다. 응시자는 연료를 $G$ 이하로 쓰면서 t에 가장 빨리 도착해야 한다.

규칙 2를 지키려면 도로 상태에 맞게 차를 몰아야 하므로, 같은 시간 $L$을 달려도 구간마다 드는 연료량이 다르다. 각 단위 구간에 적힌 정수가 그 구간을 시간 $L$ 동안 달릴 때 쓰는 연료량이다. 방향을 바꿀 때는 연료를 쓰지 않는다.

위 그림은 4행 6열 예시에서 $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 \le M, N \le 100$, $1 \le L \le 10$, $1 \le G \le 1\,000\,000$)

이어서 $M$개 줄에 걸쳐 각 줄마다 $N-1$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $i$행에서 $j$열과 $j+1$열을 잇는 가로 구간의 연료량이다. 그다음 $M-1$개 줄에 걸쳐 각 줄마다 $N$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $j$열에서 $i$행과 $i+1$행을 잇는 세로 구간의 연료량이다.

모든 단위 구간의 연료량은 1 이상 1000 이하다.

각 테스트 케이스마다 답을 한 줄에 출력한다. 연료를 $G$ 이하로 쓰면서 s에서 t까지 갈 수 있으면 가장 빨리 도착했을 때 걸리는 시간을 출력하고, 갈 수 없으면 -1을 출력한다.