给定一个 \( n \) 行 \( m \) 列的矩阵 \( A \)，其中仅包含整数。
对于每一行 \( i \)，选择一个非空区间 \( l_{i},r_{i} \)，使得相邻行的区间相交，并最大化所有区间内所有整数的总和。
形式化的，选择 \( l_{i},r_{i} \) 使得 \( 1\le l_{i} \le r_{i} \le m \)，对于所有 \( i \in \mathbb{Z} \cap [1, n) \)，满足 \( \max(l_{i},l_{i+1}) \le \min(r_{i},r_{i+1}) \)，并最大化 \( \sum_{i=1}^{n} {\sum_{j=l_{i}}^{r_{i}}{ A_{i,j} } } \)。
第一行包含一个整数 \( T \)（\( 1\le T \le 10^5 \)），表示测试用例的数量。
对于每个测试用例，第一行包含两个整数 \( n,m \)（\( 1\le n,m,n \cdot m \le 10^6 \)），表示矩阵的大小。
接下来的 \( n \) 行，每行包含 \( m \) 个整数 \( A_{i,j} \)（\( -10^9 \le A_{i,j} \le 10^9 \)），表示矩阵的每个元素。
保证 \( \sum {n \cdot m} \le 10^6 \)。
对于每组数据，一行一个整数表示答案
对于\( 20\% \)的数据，满足\( n,m \le 5 , T \le 20 \)
对于\(40\%\)的数据，满足 \(n,m,T \le 20 \)
对于\( 60\% \)的数据，满足\( n\le 1000 , m\le 20 , T\le 20 \)
对于另外 \( 20\% \)的数据，满足所有的\( A_{i} \)在\([-10^9,10^9]\)之间随机生成
对于所有数据 \( 1\leq T\leq 10^5,1\leq \sum n\cdot m \leq 10^6,-10^9 \le A_{u} \le 10^9 \)