eolymp
bolt
Try our new interface for solving problems
Problems

Hamsters and Rabbits

Hamsters and Rabbits

Time limit 1 second
Memory limit 64 MiB

In search of food big happy family of rabbits came to carrot fields. Unfortunately, just before it arrived here as a big happy family hungry hamsters. To avoid conflict, it was decided to harvest one by one. The field represents the N ridges of M bushes, on each bush growing some carrots. The next gathering will start from any shrub beds and moves first to the last, going from one bush to another by the following rule: from the bush at the garden of number of K L can proceed only on the bed of L +1 to one of the three bushes with the numbers of K-1, K , K +1 (Of course, if the bushes with such numbers exist). Each visit is cleared of bush carrot completely. The first of the harvest goes one of the rabbits, followed by hamster, rabbit and then again so until then, until the field has at least one carrot.

Rabbits are fussy, so they choose the path most profitable externally: start from the very rich shrub beds first, and from three successive versions always choose the biggest bush (with a few bushes with the same number of carrots is selected bush with the highest number). Hamsters, arriving on the field before, managed to compile a detailed map of the field and maintain it up to date on the basis of operational data on the harvest, so they each hamster choose the path that allows to collect the maximum amount of carrots from the possible (if there are several variants with maximum possible number of carrots chosen path through the bush with the highest number).

By a known map of the field, how many carrots to rabbits was able to collect and hamsters separately.

Input data

The first line of the input file contains a number of tests. Each test starts with two integers N and M (1 <= N, M <= 100). Following are N lines, each containing M numbers X _{i, j} (0 <= X _{i, j} <= 10). X _{i, j} - the number of carrots to the j-th bush i-th rows.

Output data

For each test on a separate line out through the gap of two numbers: the number of carrots collected rabbits and hamsters, respectively.

Examples

Input example #1
2
3 3
1 1 2
1 1 1
10 1 1
4 4
1 1 1 2
1 1 1 1
1 1 1 1
10 10 1 1
Output example #1
7 12
18 17
Source Школа Программиста, Красноярский край, Пятая командная олимпиада, 15 ноября 2009, Задача H