E. Finding Treasure
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a rectangular lake with dimensions $$$n$$$ and $$$m$$$. The cell $$$(i, j)$$$ of the lake has a certain depth $$$d_{i, j}$$$. The points $$$(i, j, 0), (i, j, -1), \ldots, (i, j, -d_{i, j}+1)$$$ all contain water, while the points below, such as $$$(i, j, -d_{i, j})$$$ or $$$(i, j, -d_{i, j}-1)$$$ contain rock. The rock below cell $$$(i, j)$$$ has hardness $$$h_{i, j}$$$.

You start at point $$$(a, b, 0)$$$ and want to reach treasure buried at point $$$(u, v, w)$$$. It is guaranteed that $$$(a, b, 0)$$$ contains water, but $$$(u, v, w)$$$ may contain rock.

You can navigate towards the treasure by moving in any of the six cardinal directions (forward/backward, side to side, up/down). You cannot move above the surface of the lake (i.e., to points $$$(x, y, z)$$$ with $$$z \gt 0$$$) or outside the bounds of the lake (i.e., to points $$$(x, y, z)$$$ with $$$x \le 0, x \gt n, y \le 0,$$$ or $$$y \gt m$$$). Moving to point $$$(x, y, z)$$$ takes $$$1$$$ unit of time if $$$(x, y, z)$$$ contains water, and takes $$$h$$$ units of time if $$$(x, y, z)$$$ contains rock with hardness $$$h$$$.

Find the minimum possible time you can take to reach the cell containing the treasure.

Input

Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of input test cases.

The first line of each test case contains $$$n, m$$$ ($$$1 \le n\cdot m \le 10^5$$$) — the dimensions of the lake.

The next line contains $$$a, b, u, v, w$$$ ($$$1 \le a \le n, 1 \le b \le m, 1 \le u \le n, 1 \le v \le m, 0 \le w \le 10^7$$$) — your starting position and the treasure's position.

The next $$$n$$$ lines contain the depths of the lake. The $$$i$$$th line contains $$$m$$$ integers $$$d_{i,1}, d_{i, 2}, \ldots, d_{i, m}$$$ ($$$0 \le d_{i, j} \le 10^7$$$) — the depths of the lake at each position.

The next $$$n$$$ lines contain the hardness of the rock at different parts of the lake. The $$$i$$$th line contains $$$m$$$ integers $$$h_{i,1}, h_{i, 2}, \ldots, h_{i, m}$$$ ($$$2 \le h_{i, j} \le 10$$$) — the hardness of the rock at each position.

It is further guaranteed that the sum of $$$n\cdot m$$$ over all test cases is at most $$$10^5$$$.

Output

For each test case, output a single integer — the minimum time needed for that test case.

Example
Input
3
5 5
3 5 3 3 5
5 3 5 0 3
1 2 1 0 0
0 0 0 3 1
0 2 5 0 0
0 0 0 3 5
6 9 6 7 7
3 3 7 6 2
9 10 3 3 5
5 10 8 10 9
9 8 6 6 10
5 5
5 4 3 2 4
0 5 3 0 0
3 0 3 0 2
0 4 4 3 0
4 0 4 0 4
0 0 0 2 5
3 3 2 7 5
7 8 2 8 8
8 8 3 10 8
7 4 9 10 7
10 9 3 4 6
5 5
2 4 1 4 2
0 0 1 3 4
1 5 3 3 0
5 4 0 0 0
0 4 2 1 4
0 0 2 0 0
3 2 6 5 8
3 8 7 8 9
6 4 4 3 6
5 10 8 6 6
8 7 8 2 9
Output
15
17
3