Alice's Grid Game

Alice and Bob play a turn-based game on a grid. Each cell of the grid contains a certain number of coins. The game proceeds with the players taking turns to pick a cell and collecting all coins in that cell, until there are no cells left. Both players play optimally. Since Alice plays first, she will always pick the cell with the highest number of coins available. In an optimal play the coins in all cells can be sorted in descending order, and Alice will collect coins from the cells at the even indices (0-indexed). Mathematically, if the sorted coin values are \(a_0, a_1, \dots, a_{n-1}\), then Alice's total coin collection is given by:

[ \sum_{i \text{ even}} a_i ]

Your task is to determine the maximum number of coins that Alice can collect for each test case.

inputFormat

The first line contains an integer t denoting the number of test cases. For each test case:

• The first line contains two space-separated integers N and M, which represent the number of rows and columns of the grid respectively.
• Then follow N lines, each containing M space-separated integers representing the number of coins in each cell of the grid.

All input is given via standard input (stdin).

outputFormat

For each test case, print one integer — the maximum number of coins Alice can collect — on a new line. The output is printed to standard output (stdout).

## sample

3
3 3
1 2 3
4 5 6
7 8 9
2 3
10 20 30
40 50 60
1 1
100

25
120
100

</p>