I. Crisis In Flatland
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Flatland is on the verge of collapse.

Tensions between the East and the West have reached an all-time high, and civil unrest threatens to erupt at any moment. As a last-ditch effort to save the nation, both sides have agreed to a peace negotiation — and Pranto has been elected as the neutral mediator. The negotiations are scheduled to begin soon, but there's a problem: Pranto overslept. Woken up by a call from Shanto, Pranto realizes he has very little time left to reach the Negotiation Hall on the other side of Flatland. To make matters worse, private cars have been banned in Flatland to reduce traffic congestion. Now, Pranto must rely entirely on public transportation.

Flatland is organized as a grid of size $$$n \times m$$$, where each cell is a city. Pranto starts at city $$$u$$$, and the Negotiation Hall is at city $$$v$$$. A city is identified as a pair $$$(r, c)$$$, representing the city in the $$$r$$$-th row and $$$c$$$-th column. Additionally, each city has a boarding cost $$$B_{r,c}$$$ and a traffic jam $$$J_{r,c}$$$.

There are two types of public transport in Flatland:

  • Trains travel horizontally between any two cities in the same row. A train ride takes exactly the horizontal distance between the start and end cities. Formally, you can go from a city $$$(r, c_1)$$$ to another city in the same row $$$(r, c_2)$$$ in time $$$|c_2 - c_1|$$$ using a train.

  • Buses travel vertically between any two cities in the same column. A bus ride takes the vertical distance between the start and end cities plus the total traffic jam from all intermediate cities on that column, not including the endpoints. Formally, you can go from a city $$$(r_1, c)$$$ to another city in the same column $$$(r_2, c)$$$ in time $$$|r_2 - r_1| + \displaystyle\sum_{r = \min(r_1, r_2) + 1}^{\max(r_1, r_2) - 1} J_{r,c}$$$.

To board a train or a bus at city $$$(r, c)$$$, Pranto must pay a boarding cost of $$$B_{r,c}$$$. This cost is the same regardless of the destination or travel distance.

Your task is to help Pranto find the minimum total cost to reach the Negotiation Hall within at most $$$T$$$ units of time, or report that it is impossible.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.

The first line of each test case contains seven space-separated integers $$$n$$$, $$$m$$$, $$$r_u$$$, $$$c_u$$$, $$$r_v$$$, $$$c_v$$$, and $$$T$$$ $$$(2 \le n, m \le 500,\ 1 \le r_u, r_v \le n,\ 1 \le c_u, c_v \le m,\ 0 \le T \le 10^9)$$$ — the number of rows and columns in Flatland, the row and column of the starting city $$$u$$$, the row and column of the destination city $$$v$$$, and the maximum allowed time.

The next $$$n$$$ lines each contain $$$m$$$ space-separated integers $$$(1 \le B_{r,c} \le 10^3)$$$ — the boarding cost matrix. The $$$c$$$-th integer in the $$$r$$$-th line denotes $$$B_{r,c}$$$.

The following $$$n$$$ lines each contain $$$m$$$ space-separated integers $$$(0 \le J_{r,c} \le 10^9)$$$ — the traffic jam matrix. The $$$c$$$-th integer in the $$$r$$$-th line denotes $$$J_{r,c}$$$.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^3$$$, and that the sum of all boarding costs in a single test case does not exceed $$$10^4$$$.

Output

For each test case, output a single integer:

The minimum total boarding cost required to reach the destination city within at most $$$T$$$ units of time. If it is not possible, output $$$-1$$$.

Example
Input
6
3 3 1 1 3 3 4
1 100 100
1 1 100
100 1 1
0 0 0
0 0 0
0 0 0
3 3 1 1 3 3 4
1 1 1
100 1 100
1 1 1
0 100 0
0 0 0
0 100 0
3 3 1 1 3 3 4
1 1 1
1 1 1
1 1 1
0 0 0
100 0 100
0 0 0
3 3 1 1 3 3 4
1 1 1
100 1 100
1 1 1
0 0 0
100 100 100
0 0 0
3 3 1 1 3 3 4
1 1 1
100 100 100
1 1 1
0 0 0
100 100 100
0 0 0
3 3 1 1 3 3 3
1 1 1
100 100 100
1 1 1
0 0 0
100 100 100
0 0 0
Output
4
2
3
4
102
-1