{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\r\nGiven an \u003cb\u003en\u003c/b\u003e*\u003cb\u003em\u003c/b\u003e board with a number between -1 and \u003cb\u003en\u003c/b\u003e*\u003cb\u003em\u003c/b\u003e in every entries.\r\n\r\n\u003cp\u003eAnd an \u003cb\u003en\u003c/b\u003e*\u003cb\u003em\u003c/b\u003e matrix \u003cb\u003eM\u003c/b\u003e is also given, where \u003cb\u003eM\u003c/b\u003e\u003csub\u003ei,j\u003c/sub\u003e is the cost of selecting the \u003ci\u003e(i,j)\u003c/i\u003e entry of the given board.\r\n\r\n\u003cp\u003eYour task is to find a connected block (which means these entries can reach each other by just go up, down, left and right without going out the block) in the board that contains at least \u003cb\u003eK\u003c/b\u003e distinct positive numbers without any -1, and it must have minimum total cost for selecting these entries. Output the minimum total cost.\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line consists of three integers, \u003cb\u003en\u003c/b\u003e, \u003cb\u003em\u003c/b\u003e, \u003cb\u003eK\u003c/b\u003e (1 \u003c\u003d \u003cb\u003en\u003c/b\u003e, \u003cb\u003em\u003c/b\u003e \u003c\u003d 15, 1 \u003c\u003d \u003cb\u003eK\u003c/b\u003e \u003c\u003d 7).\r\n\r\n\u003cp\u003eThe followings are two \u003cb\u003en\u003c/b\u003e*\u003cb\u003em\u003c/b\u003e matrices, the first denotes the numbers on the board and the second denotes the cost of every entry.\r\n\r\n\u003cp\u003eNamely, the first \u003cb\u003en\u003c/b\u003e lines contain \u003cb\u003em\u003c/b\u003e integers, where the \u003ci\u003ej\u003c/i\u003eth number in \u003ci\u003ei\u003c/i\u003eth line denotes the number on the entry (\u003ci\u003ei\u003c/i\u003e,\u003ci\u003ej\u003c/i\u003e) of the board. These integers are in [-1, \u003cb\u003en\u003c/b\u003e*\u003cb\u003em\u003c/b\u003e].\r\n\r\n\u003cp\u003eNext \u003cb\u003en\u003c/b\u003e lines contain \u003cb\u003em\u003c/b\u003e integers too. The \u003ci\u003ej\u003c/i\u003eth number in \u003ci\u003ei\u003c/i\u003eth line denotes the cost of selecting the entry (\u003ci\u003ei\u003c/i\u003e,\u003ci\u003ej\u003c/i\u003e) of the board. These integers are in [1, 100000].\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nOnly one line contains the minimum cost to finish the task. If the task is impossible, output -1 please.\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n3 3 3\r\n0 0 1 \r\n2 3 3 \r\n-1 2 1 \r\n3 1 5 \r\n4 10 1 \r\n9 3 4 \r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n8\r\n\u003c/pre\u003e\r\n"}}]}