Hamsters and Rabbits#430
In search of food, a big happy family of rabbits arrived at a carrot field. Unfortunately, just before them, a big happy family of hungry hamsters also arrived. To avoid conflict, it was decided to harvest the field in turns. The field consists of rows, each with bushes; each bush contains some number of carrots. A harvester starts from any bush in the first row and moves towards the last row, moving from one bush to another according to the following rule: from bush number in row , you can move only to row l + 1 to one of the three bushes with numbers k - 1, , or k + 1 (if bushes with such numbers exist). Each visited bush is completely cleared of carrots. The first to harvest is a rabbit, then a hamster, then a rabbit again, and so on, until there is at least one carrot left in the field.
Rabbits are hasty, so they choose the most apparently profitable path: they start from the richest bush in the first row and, at each step, from the three options, always choose the bush with the largest number of carrots (if several bushes have the same number of carrots, they choose the one with the highest number). The hamsters, having arrived earlier, managed to create a detailed map of the field and maintain it based on the updated harvest data, so each hamster chooses the path that allows it to collect the maximum possible carrots (if there are several options with the same maximum number, the path through the bush with the highest number is chosen).
Given the map of the field, determine how many carrots the rabbits and the hamsters are able to collect separately.
The first line contains the number of tests. Each test begins with two integers and (1 \leq n, m \leq 100). Then follow lines, each containing integers x_{i,j} (0 \leq x_{i,j} \leq 10). x_{i,j} is the number of carrots at the -th bush of the -th row.
For each test, output on a separate line two numbers: the number of carrots collected by the rabbits and by the hamsters, respectively.
Example 1