{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003clink href\u003d\"css/light_oj.css\" rel\u003d\"stylesheet\" type\u003d\"text/css\" /\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tIts year 2200, planet Earth is out of resources and people are relying on the resources from other planets. There are several Refining Companies who collect these resources from other planets and bring them back to Earth. The task may sound simple, but in reality it\u0026#39;s a challenging job. The resources are scattered and after collecting them, they have to be taken to a place where they can be refined. Since some minerals are extremely dangerous, the whole process should be done very carefully. A single tiny mistake can cause a massive explosion resulting in a huge loss.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tYou work in such a company who collects Uranium and Radium from planet Krypton. These minerals are used for generating powers. For simplicity you have divided planet Krypton into cells that form a matrix of m rows and n columns, where the rows go from east to west and the columns go from north to south. Your advanced mine detector has detected the approximate amount of Radium and Uranium in each cell. Your company has built two refining factories, one in West and the other in North. The factory in North is used to refine Radium and the factory in West is used to refine Uranium. Your task is to design the conveyor belt system that will allow them to mine the largest amount of minerals.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tThere are two types of conveyor belts: the first moves minerals from east to west, the second moves minerals from south to north. In each cell you can build either type of conveyor belt, but you cannot build both of them in the same cell. If two conveyor belts of the same type are next to each other, then they can be connected. For example, the Radium mined at a cell can be transported to the Radium refinement factory via a series of south-north conveyor belts.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tThe minerals are very unstable, thus they have to be brought to the factories on a straight path without any turns. This means that if there is a south-north conveyor belt in a cell, but the cell north of it contains an east-west conveyor belt, then any mineral transported on the south-north conveyor belt will be lost. The minerals mined in a particular cell have to be put on a conveyor belt immediately; in the same cell (thus they cannot start the transportation in an adjacent cell). Furthermore, any Radium transported to the Uranium refinement factory will be lost, and vice versa.\u003c/p\u003e\r\n\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"text-align:center\"\u003e\r\n\t\u003cimg id\u003d\"Picture 1\" src\u003d\"http://oi39.tinypic.com/2evw7qq.jpg\" style\u003d\"width: 267px; height: 165px;\" /\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tYour program has to design a conveyor belt system that maximizes the total amount of minerals mined, i.e., the sum of the amount of Radium transported to the Radium refinery and the amount of Uranium to the Uranium refinery.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e\u0026le; 10)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tEach case begins with a blank line and two integers: \u003cb\u003em\u003c/b\u003e - the number of rows, and \u003cb\u003en\u003c/b\u003e - the number columns \u003cb\u003e(1 \u0026le; m, n \u0026le; 500)\u003c/b\u003e. The next \u003cb\u003em\u003c/b\u003e lines describe the amount of Uranium that can be found in the cells. Each of these \u003cb\u003em\u003c/b\u003e lines contains \u003cb\u003en\u003c/b\u003e integers. The first line corresponds to the northernmost row; the first integer of each line corresponds to the westernmost cell of the row. The integers are between \u003cb\u003e0\u003c/b\u003e and \u003cb\u003e1000\u003c/b\u003e. The next \u003cb\u003em\u003c/b\u003e lines describe in a similar fashion the amount of Radium found in the cells. Data set is huge, so use faster i/o methods.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\u003cspan style\u003d\"line-height:115%;font-family:\u0026quot;Times New Roman\u0026quot;,\u0026quot;serif\u0026quot;;\r\ncolor:black\"\u003eFor each case of input you have to print the case number and the maximum amount of minerals you can collect.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 4\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 0 10 9\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 3 10 0\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 2 1 3 \u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 1 20 0\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e10 0 0 0\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 1 1 30\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 0 5 5\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e5 10 10 10\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e5 10 34\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 0 0\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 0 0\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e50 0 0\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 98\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 50\u003c/span\u003e\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tDataset is huge. Use faster I/O methods.\u003c/p\u003e"}}]}