{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e You are in the world of mathematics to solve the great \"Monkey Banana Problem\". It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells \u003cb\u003edown\u003c/b\u003e from its current position (see figure). While moving from one cell to another, the monkey eats all the bananas kept in that cell. The monkey enters into the array from the upper part and goes out through the lower part. Find the maximum number of bananas the monkey can eat.\u003c/p\u003e \n\u003cp\u003e \u003cimg src\u003d\"http://www.lightoj.com/data/problems/desc/1004/a.png\"\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e Input starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 50)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e \n\u003cp\u003e Every case starts with an integer \u003cb\u003eN (1 ≤ N ≤ 100)\u003c/b\u003e. It denotes that, there will be \u003cb\u003e2*N - 1\u003c/b\u003e rows. The \u003cb\u003e\u003cspan\u003ei\u003csup\u003eth\u003c/sup\u003e\u003c/span\u003e (1 ≤ i ≤ N)\u003c/b\u003e line of next \u003cb\u003eN\u003c/b\u003e lines contains exactly \u003cb\u003ei\u003c/b\u003e numbers. Then there will be \u003cb\u003eN - 1\u003c/b\u003e lines. The \u003cb\u003e\u003cspan\u003ej\u003csup\u003eth\u003c/sup\u003e\u003c/span\u003e (1 ≤ j \u0026lt; N)\u003c/b\u003e line contains \u003cb\u003eN - j\u003c/b\u003e integers. Each number is greater than zero and less than \u003cb\u003e2\u003csup\u003e15\u003c/sup\u003e\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e For each case, print the case number and maximum number of bananas eaten by the monkey.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e4\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e7\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e6 4\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2 5 10\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e9 8 12 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2 12 7\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e8 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e10\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e1\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2 3\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e1\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eCase 1: 63\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eCase 2: 5\u003c/span\u003e\u003c/p\u003e"}}]}