{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/8f455915740e1a81600842e37745fd34?v\u003d1721749549\"\u003e\u003cbr\u003e\n\tTom\u0027s Meadow\u003cbr\u003e\n\u003c/center\u003e\n\u003cp\u003e\n Tom has a meadow in his garden. He divides it into \u003ci\u003eN\u003c/i\u003e * \u003ci\u003eM\u003c/i\u003e squares. \nInitially all the squares are covered with grass and there may be some squares cannot be mowed.(Let\u0027s call them forbidden squares.)\nHe wants to mow down the grass on some of the squares.\nHe must obey all these rules:\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\n\u003cb\u003e\n1 He can start up at any square that can be mowed. \u003cbr\u003e\n2 He can end up at any square that can be mowed.\u003cbr\u003e\n3 After mowing one square he can get into one of the adjacent squares. \u003cbr\u003e\n4 He cannot get into any of the forbidden squares.\u003cbr\u003e\n5 He cannot get into the squares that he has already mowed.\u003cbr\u003e\n6 If he is in some square he must mow it first. (and then decide whether to mow the adjacent squares or not.)\u003cbr\u003e\n7 Each square that can be mowed has a property \u003ci\u003eD\u003c/i\u003e called beauty degree (\u003ci\u003eD\u003c/i\u003e is a positive integer) and if he mowed the square the beauty degree of the meadow would increase by \u003ci\u003eD\u003c/i\u003e.\u003cbr\u003e\n8 Note that the beauty degree of the meadow is 0 at first.\u003cbr\u003e\n9 Of course he cannot move out of the meadow. (Before he decided to end.)\u003cbr\u003e\n\u003c/b\u003e\n Two squares are adjacent if they share an edge.\n\u003c/p\u003e\n\n\u003cp\u003e\nHere comes the problem. What is the maximum beauty degree of the meadow Tom can get without breaking the rules above.\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nThis problem has several test cases. \nThe first line of the input is a single integer \u003ci\u003eT\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eT\u003c/i\u003e \u0026lt; 60) which is the number of test cases. \u003ci\u003eT\u003c/i\u003e consecutive test cases follow. \nThe first line of each test case is a single line containing 2 integers \u003ci\u003eN\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eN\u003c/i\u003e \u0026lt; 8) and \u003ci\u003eM\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eM\u003c/i\u003e \u0026lt; 8) which is the number of rows of the meadow and the number of columns of the meadow.\nThen \u003ci\u003eN\u003c/i\u003e lines of input describing the rows of the meadow.\nEach of the \u003ci\u003eN\u003c/i\u003e lines contains \u003ci\u003eM\u003c/i\u003e space-separated integers \u003ci\u003eD\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003eD\u003c/i\u003e \u0026lt;\u003d 60000) indicating the beauty degree of the correspoding square.\n\u003cb\u003e\n For simplicity the beauty degree of forbidden squares is 0. (And of course Tom cannot get into them or mow them.)\n\u003c/b\u003e\n\u003c/p\u003e\n\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nFor each test case output an integer in a single line which is maximum beauty degree of the meadow at last.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e2\n1 1\n10\n1 2\n5 0\n\u003c/pre\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e10\n5\n\u003c/pre\u003e\n\n"}}]}