Sum of Row Maximums

You are given a matrix with \(N\) rows and \(M\) columns, where each cell contains a non-negative integer. Your task is to select exactly one cell from each row. Unlike typical assignment problems, the cells selected in different rows can be in the same column. Thus, the optimal strategy is simply to pick the maximum element from each row.

Formally, let \(a_{ij}\) denote the element in the \(i\)-th row and \(j\)-th column. For each row \(i\) (\(1 \le i \le N\)), define \(m_i = \max_{1 \le j \le M} a_{ij}\). The answer is given by:

[ \text{Answer} = \sum_{i=1}^{N} m_i ]

You need to process \(T\) test cases. For each test case, output the computed answer on a separate line.

inputFormat

The input is given from standard input (stdin) and consists of multiple test cases.

• The first line contains a single integer \(T\) representing the number of test cases.
• For each test case:
  • The first line contains two integers \(N\) and \(M\), denoting the number of rows and columns respectively.
  • The next \(N\) lines each contain \(M\) space-separated non-negative integers, representing the rows of the matrix.

outputFormat

For each test case, output a single line containing one integer: the sum of the maximum values of each row.

Output the results to standard output (stdout). When there are multiple test cases, the answers should be printed on separate lines in the order of the input test cases.

1
2 2
1 2
3 4

6