{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"All of you must have heard the name of Baker Vai. Yes, he rides a bike and likes to help people. That\u0027s why he is popular amongst general people.\n\nBaker Vai lives in a city which can be modeled as a 2D **m x n** matrix. Where the north-west corner is cell **1, 1** and the south-east corner is cell **m, n**. In each cell there are certain amount of people who needs help which is already known to Baker Vai.\n\nEach day Baker Vai starts his journey from the north-west corner and he can only go to east or south. This way he reaches the south-east corner of the city. After that he returns back to the north-west, but this time he can only move to west or north. He doesn\u0027t want a cell to be visited twice other than the two corners. And if he visits a cell, he helps all the people in the cell.\n\nNow you are given the map of the city and the number of people who need help in all cells for a particular day. You have to help Baker Vai finding the maximum number of people he can help in that day.\n"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 25)**, denoting the number of test cases.\n\nEach case contains a blank line and two integers, **m, n (2 \u0026#8804; m, n \u0026#8804; 100)**. Each of the next **m** lines will contain **n** integers, denoting the number of people who are in need. In a cell there will be no more than **20** people and a cell can be empty, too.\n"}},{"title":"Output","value":{"format":"MD","content":"For each test case, print the case number and the maximum number of people Baker Vai can help considering the above conditions."}},{"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\u003e2\n\n3 3\n1 1 1\n1 0 1\n1 1 1\n\n3 4\n1 1 0 1\n1 1 1 1\n0 1 10 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 8\nCase 2: 18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}