Driving license test

A driving license test is held on a course laid out as a grid with $M$ rows and $N$ columns.

The test has three rules.

• Rule 1: The candidate starts at the top left point s and drives east (right) and south (down) only, until reaching the bottom right point t.
• Rule 2: Driving one grid segment straight takes time $L$, the same going right and going down. $L$ is a constant fixed before the test. Changing direction always takes time 1. At the start point s the candidate can pick either right or down, and that first choice costs no time.
• Rule 3: The car is filled with $G$ fuel before the test. The candidate must reach t as early as possible while using at most $G$ fuel.

Following rule 2 means driving to suit the state of the road, so the fuel spent over the same time $L$ differs from segment to segment. The integer written on a unit segment is the fuel it takes to drive that segment for time $L$. Changing direction takes no fuel.

The picture above draws two routes that work on the 4 row 6 column example when $G = 19$ and $L = 10$. The left route spends 17 fuel and arrives at time 83. It drives 8 unit segments straight and changes direction 3 times. The right route spends only 16 fuel, but it changes direction more often, so its time is 85. A few other routes also arrive at time 83 with at most 19 fuel. No route arrives at t earlier than time 83 while using at most 19 fuel.

Given the state of the grid together with $G$ and $L$, find the earliest time to reach t.

The first line has the number of test cases $T$.

The first line of each test case has four integers $M$, $N$, $L$ and $G$. $M$ is the number of rows of the grid, $N$ is the number of columns, $L$ is the time to drive one unit segment straight, and $G$ is the amount of fuel. ($2 \le M, N \le 100$, $1 \le L \le 10$, $1 \le G \le 1\,000\,000$)

Then come $M$ lines with $N-1$ integers each. The $j$-th integer on the $i$-th line is the fuel of the horizontal segment that joins column $j$ and column $j+1$ in row $i$. After that come $M-1$ lines with $N$ integers each. The $j$-th integer on the $i$-th line is the fuel of the vertical segment that joins row $i$ and row $i+1$ in column $j$.

Every unit segment takes between 1 and 1000 fuel.

For each test case print the answer on its own line. If s to t is possible with at most $G$ fuel, print the earliest arrival time. Otherwise print -1.