402863: GYM100923 G Por Costel and the Orchard

Por Costel has discovered a writing from porcine mythology: "The Ballad of the Pig". The ballad describes a love story between a boar and a gilt. In one of the chapters, the boar tries to impress his significant other by erecting a pig pen. He fails, being tragically limited by his porcine nature. But then the ballad continues saying that the pig eventually found a fabulous orchard in the middle of a forest which he took as a home for himself and the gilt.

Por Costel is, however, not impressed by either forced rhymes, or exaggerated figurative speech. "A forest is full of orchards" he says. "It's just a matter of how you choose it".

You are provided with an x matrix which describes a "forest". Each cell has an integer value - the degree of its beauty. You are tasked with choosing an "orchard", meaning a subset of cells that satisfies the following conditions:

• It is non-empty
• It is connected(you can get from any cell to any other cell by passing only through cells that have a common side)
• The intersection of the subset with any row of the matrix is either empty, or a connected(the same of definition as above) subset of cells. In other words, on each row, the subset should have either no cell, or a continuous interval of cells.

The beauty of an orchard is defined as the sum of its cells' beauty degrees. Out of all orchards, pick the one with maximum beauty

The input livada2.in will contain on the first line (), the number of tests.

Each of the tests has the following format: on the first line there will be two natural numbers and , the number of rows and the number of columns of the matrix ().

Each of the next lines will contain integers separated by spaces. The -th number of the -th line will be the beauty degree of cell (

The output file livada2.out will contain lines and each of these lines will contain a single integer number, the maximum beauty of an orchard.

1
3 4
5 -3 0 0
-2 3 3 4
-7 -6 4 -5

17