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) sqares 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 testcases.
The first line of each testcase contains 2 ≤ N ≤ 17, the size of big square.
Each of the next N lines contain N integers, the heigths 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 testcase 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 testcase
000: 0 100: 0 010: 0 001: 0 110: 2 101: 3 011: 3 111: 4
For the second testcase, each subset costs 0, unless those, which consists of last Tyg3R (and some other)  those cost 2.
The third testcase has only one valuable subset (of both Tyg3Rs), which goes on top/right border, and costs 8.
hide comments
Rohit Agarwal:
20181116 17:41:54
@morass: Loved this problem! Learn't something new! 

v_pal:
20180831 14:26:03
Need a little help can't figure out how to approach the problem ? 

morass:
20170527 12:46:36
@lu: No clue, try to ask leader of local zoo :P (+1)


lu:
20170526 17:53:25
steiner tree？ 

morass:
20170406 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.


mahmud2690:
20170405 23:52:02
@morass: Is intended solution is O(T*(Q!))? 

Vipul Srivastava:
20170405 18:33:55
Last edit: 20170405 18:35:03 

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

[Rampage] Blue.Mary:
20170404 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:  20170404 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 