No Smoking, Please

Time limit3sMemory limit512 MB

Summary

Given a grid whose adjacent rooms are joined by passages of known area, split rooms into two connected zones separating entrance from kitchen, paying 1000 per unit passage area plus 1000 per cut passage.

Level: Hard8 of 10
Topics: Graph, Minimum spanning tree, Greedy
Solved: No attempts yet

Problem

Anti-smoking laws are in effect, and nearly every restaurant has had to change its interior so that smoking and non-smoking customers can be seated in separate parts of the building.

Johann, the owner of a restaurant, has decided to divide his restaurant into two zones connected by air locks. Each air lock also carries a hatch so that food can be passed through, because the staff may not enter the smoking zone. The smoking zone will be connected directly to the outside (saving on heating and providing fresh air), while the non-smoking zone must be connected to the kitchen so that the staff can serve food.

The restaurant is a rectangular grid of equally sized square rooms. Each room may be connected to its (at most four) neighbouring rooms by a passage. To split the restaurant into the two zones, Johann installs an air lock in some of the passages that connect two rooms.

Costs:

An air lock costs 1000 euros per square metre of the passage it is installed in.
Each air lock also needs a hatch, which costs 1000 euros.

So installing an air lock in a passage whose area is $a$ square metres costs $1000 \cdot a + 1000$ euros. A wall that has no passage (area 0) needs neither an air lock nor a hatch, so it costs nothing.

The room connected to the entrance must end up in the smoking zone, and the room connected to the kitchen must end up in the non-smoking zone. Every passage that connects a room in the smoking zone to a room in the non-smoking zone must have an air lock (with a hatch); passages that stay inside a single zone need nothing.

Help Johann split the restaurant into the two zones so that the total cost is as small as possible.

Input

The first line contains a positive integer, the number of test cases. Each test case is given as follows:

A line with two positive integers $nr$ and $nc$ ( $nr, nc < 1000$ ): the number of rows and columns of rooms.
A line with two integers $er$ and $ec$ ( $0 \le er < nr$ , $0 \le ec < nc$ ): the row and column of the room connected to the entrance.
A line with two integers $kr$ and $kc$ ( $0 \le kr < nr$ , $0 \le kc < nc$ ): the row and column of the room connected to the kitchen.
$nr$ lines, each with $nc - 1$ non-negative integers below 100. The $j$ -th integer on line $i$ is the area (in square metres) of the passage between room $(i, j)$ and room $(i, j+1)$ .
$nr - 1$ lines, each with $nc$ non-negative integers below 100. The $j$ -th integer on line $i$ is the area (in square metres) of the passage between room $(i, j)$ and room $(i+1, j)$ .

An area of 0 means there is no passage (a solid wall) between those two rooms.

Output

For each test case, print a single line with the minimum total cost, in euros, of dividing the restaurant into the two zones so that the entrance room is in the smoking zone and the kitchen room is in the non-smoking zone.

Examples6

Example 1

Input

Expected output

2000
4000

Example 2
Input
```
1
1 2
0 0
0 1
5
```
Expected output
```
6000
```
Example 3
Input
```
1
1 4
0 0
0 3
3 1 4
```
Expected output
```
2000
```
Example 4
Input
```
1
4 1
0 0
3 0




2
5
1
```
Expected output
```
2000
```
Example 5
Input
```
1
2 2
0 0
1 1
0
5
2 0
```
Expected output
```
3000
```
Example 6
Input
```
1
2 2
0 0
1 1
2
99
3 99
```
Expected output
```
7000
```