{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/8f455915740e1a81600842e37745fd34?v\u003d1679640809\"\u003e\u003cbr\u003e\n Tom\u0027s Meadow\u003cbr\u003e\n\u003c/center\u003e\n\u003cp\u003eTom has a meadow in his garden. He divides it into \u003ci\u003eN\u003c/i\u003e * \u003ci\u003eM\u003c/i\u003e squares. Initially all the squares are covered with grass and there may be some squares cannot be mowed.(Let\u0027s call them forbidden squares.) He wants to mow down the grass on some of the squares. He must obey all these rules:\u003cbr\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e 1 He can start up at any square that can be mowed. \u003cbr\u003e\n 2 He can end up at any square that can be mowed.\u003cbr\u003e\n 3 After mowing one square he can get into one of the adjacent squares. \u003cbr\u003e\n 4 He cannot get into any of the forbidden squares.\u003cbr\u003e\n 5 He cannot get into the squares that he has already mowed.\u003cbr\u003e\n 6 If he is in some square he must mow it first. (and then decide whether to mow the adjacent squares or not.)\u003cbr\u003e\n 7 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\n 8 Note that the beauty degree of the meadow is 0 at first.\u003cbr\u003e\n 9 Of course he cannot move out of the meadow. (Before he decided to end.)\u003cbr\u003e\u003c/b\u003e Two squares are adjacent if they share an edge.\u003c/p\u003e\n\u003cp\u003eHere comes the problem. What is the maximum beauty degree of the meadow Tom can get without breaking the rules above.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThis problem has several test cases. The 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. The 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. Then \u003ci\u003eN\u003c/i\u003e lines of input describing the rows of the meadow. Each 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. \u003cb\u003e For simplicity the beauty degree of forbidden squares is 0. (And of course Tom cannot get into them or mow them.) \u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eFor each test case output an integer in a single line which is maximum beauty degree of the meadow at last.\u003c/p\u003e\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"}}]}