ADAZOO - Ada and Zoo


Ada the Ladybug is a well know farmer. As she has experience with building fences and breeding animals, she was asked by leader of local zoo - Lichsteiner Leech - to help them design a paddock for animals.

The problem is following: The zoo breeds very rare beasts called Tyg3Rs. There are few of them in a N x N square paddock with squares have different heights. The Tyg3Rs live in (little) squares and the breeders want them to play with each other. At first it is not possible to travel between distinct squares, but it is possible to connect any two adjacent squares for cost of absolute difference of their heights (by making slope).

Now, for each subset of Tyg3Rs, the zoo wants to know minimal price to connect the squares in such way, that each Tyg3R can get to each other. As the output would be pretty big, they just want you to sum these costs.

As her good friend (and as the instances are too big for her to handle), she has asked you to help her with this problem.

Input

The first line contains T, the number of test-cases.

The first line of each test-case contains 2 ≤ N ≤ 17, the size of big square.

Each of the next N lines contain N integers, the heights of each square. Each number is between 0 and 1000.

The next line contains 1 ≤ Q ≤ 10, the number of Tyg3Rs.

The next Q lines contains two integers: 0 ≤ x, y < N, the coordinates of Tyg3Rs. Note that multiple Tyg3Rs might already live in the same square.

Output

For each test-case print the sum of costs of cheapest way to connect all subset of Tyg3Rs.

Example Input

4
3
1 2 1
2 1 2
1 2 1
3
0 0
0 2
2 1
3
5 5 5
7 5 5
3 4 4
4
0 0
0 0
0 0
2 0
3
1 2 3
4 5 6
7 8 9
2
0 0
2 2
8
1 8 5 2 3 6 7 4
1 5 7 5 4 6 8 7
9 8 7 4 5 2 3 6
1 4 5 7 2 5 3 6
5 2 1 2 4 5 8 5
9 9 9 9 6 6 4 5
2 2 3 4 9 1 9 1
1 4 1 4 7 5 2 1
5
0 0
5 6
3 3
2 1
7 7

Example Output

12
14
8
441

Input Explanation

Prices of subsets of first test-case

000: 0
100: 0
010: 0
001: 0
110: 2
101: 3
011: 3
111: 4

For the second test-case, each subset costs 0, unless those, which consists of last Tyg3R (and some other) - those cost 2.

The third test-case has only one valuable subset (of both Tyg3Rs), which goes on top/right border, and costs 8.


hide comments
Rohit Agarwal: 2018-11-16 17:41:54

@morass: Loved this problem! Learn't something new!

v_pal: 2018-08-31 14:26:03

Need a little help can't figure out how to approach the problem ?

morass: 2017-05-27 12:46:36

@lu: No clue, try to ask leader of local zoo :P (+1)

Have nice day ^_^

lu: 2017-05-26 17:53:25

steiner tree?

morass: 2017-04-06 02:26:32

@mahmud2690: Hello, nope it is not. Even though I don't know where you "aim", if the complexity would be "clean", it might pass.

To constrains -it is hard for me to "write it correctly" since there are different types of test-cases:

A) Either "small/random" test-cases (T is up to 100)

B) Big test-cases (T is up to 10)


Good Luck!

~/Morass

mahmud2690: 2017-04-05 23:52:02

@morass: Is intended solution is O(T*(Q!))?

morass: 2017-04-04 11:35:59

@[Rampage] Blue.Mary: You are right, all the samples were wrong [for a reason] - sorry for inconvenience / thanx! ^_^

[Rampage] Blue.Mary: 2017-04-04 07:58:52

As you've already listed in the explanation section, the output for the first test case should be 2+3+3+4 = 12?


Added by:Morass
Date:2017-04-04
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All