{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOn an \u003ci\u003eN\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e chessboard with a non-negative number in each grid, Kaka starts his matrix travels with \u003ci\u003eSUM\u003c/i\u003e \u003d 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to \u003ci\u003eSUM \u003c/i\u003ein each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum \u003ci\u003eSUM\u003c/i\u003e Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum \u003ci\u003eSUM\u003c/i\u003e he can obtain after his \u003ci\u003eK\u003c/i\u003eth travel. Note the \u003ci\u003eSUM\u003c/i\u003e is accumulative during the \u003ci\u003eK\u003c/i\u003e travels.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eK\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 50, 0 ≤ \u003ci\u003eK\u003c/i\u003e ≤ 10) described above. The following \u003ci\u003eN\u003c/i\u003e lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe maximum \u003ci\u003eSUM\u003c/i\u003e Kaka can obtain after his \u003ci\u003eK\u003c/i\u003eth travel.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3 2\r\n1 2 3\r\n0 2 1\r\n1 4 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}