{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eAda 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.\u003c/p\u003e\r\n\u003cp\u003eThe problem is following: The zoo breeds very rare beasts called Tyg3Rs. There are few of them in a \u003cstrong\u003eN x N\u003c/strong\u003e 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).\u003c/p\u003e\r\n\u003cp\u003eNow, 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.\u003c/p\u003e\r\n\u003cp\u003eAs her good friend (and as the instances are too big for her to handle), she has asked you to help her with this problem.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains \u003cstrong\u003eT\u003c/strong\u003e, the number of test-cases.\u003c/p\u003e\r\n\u003cp\u003eThe first line of each test-case contains \u003cstrong\u003e2 ≤ N ≤ 17\u003c/strong\u003e, the size of big square.\u003c/p\u003e\r\n\u003cp\u003eEach of the next \u003cstrong\u003eN\u003c/strong\u003e lines contain \u003cstrong\u003eN\u003c/strong\u003e integers, the heights of each square. Each number is between \u003cstrong\u003e0\u003c/strong\u003e and \u003cstrong\u003e1000\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003eThe next line contains \u003cstrong\u003e 1 ≤ Q ≤ 10\u003c/strong\u003e, the number of Tyg3Rs.\u003c/p\u003e\r\n\u003cp\u003eThe next \u003cstrong\u003eQ\u003c/strong\u003e lines contains two integers: \u003cstrong\u003e0 ≤ x, y \u0026lt; N\u003c/strong\u003e, the coordinates of Tyg3Rs. Note that multiple Tyg3Rs might already live in the same square.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test-case print the sum of costs of cheapest way to connect all subset of Tyg3Rs.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n3\r\n1 2 1\r\n2 1 2\r\n1 2 1\r\n3\r\n0 0\r\n0 2\r\n2 1\r\n3\r\n5 5 5\r\n7 5 5\r\n3 4 4\r\n4\r\n0 0\r\n0 0\r\n0 0\r\n2 0\r\n3\r\n1 2 3\r\n4 5 6\r\n7 8 9\r\n2\r\n0 0\r\n2 2\r\n8\r\n1 8 5 2 3 6 7 4\r\n1 5 7 5 4 6 8 7\r\n9 8 7 4 5 2 3 6\r\n1 4 5 7 2 5 3 6\r\n5 2 1 2 4 5 8 5\r\n9 9 9 9 6 6 4 5\r\n2 2 3 4 9 1 9 1\r\n1 4 1 4 7 5 2 1\r\n5\r\n0 0\r\n5 6\r\n3 3\r\n2 1\r\n7 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\r\n14\r\n8\r\n441\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003ch3\u003eInput Explanation\u003c/h3\u003e\r\n\u003cp\u003ePrices of subsets of first test-case\u003c/p\u003e\r\n\u003cpre\u003e000: 0\r\n100: 0\r\n010: 0\r\n001: 0\r\n110: 2\r\n101: 3\r\n011: 3\r\n111: 4\r\n\u003c/pre\u003e\r\n\u003cp\u003eFor the second test-case, each subset costs 0, unless those, which consists of last Tyg3R (and some other) - those cost 2.\u003c/p\u003e\r\n\u003cp\u003eThe third test-case has only one valuable subset (of both Tyg3Rs), which goes on top/right border, and costs 8.\u003c/p\u003e\n\u003c/div\u003e"}}]}