Intersecting Intervals
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

You are given a matrix A of n rows and m columns, containing only integers.

For each row i, choose a non-empty interval l_{i},r_{i}, such that the adjacent row's interval intersects, and maximize the sum of all integers over all intervals.

Formally, choose l_{i},r_{i} such that 1\le l_{i} \le r_{i} \le m, \max(l_{i},l_{i+1}) \le \min(r_{i},r_{i+1}) for all i \in \mathbb{Z} \cap [1, n), and maximize \sum_{i=1}^{n} {\sum_{j=l_{i}}^{r_{i}}{ A_{i,j} } }

输入描述:

The first line contains one integer T (1\le T \le 10^5), representing the number of test cases.

For each test case, the first line contains two integers n,m (1\le n,m,n \cdot m \le 10^6), representing the size of the matrix.

The following n lines, each contain m integers A_{i,j} (-10^9 \le A_{i,j} \le 10^9), representing each element of the matrix.

It is guaranteed that \sum {n \cdot m} \le 10^6.

输出描述:

For each test case, output one line containing a single integer, representing the answer.
示例1

输入

复制 
5
4 4
-1 1 1 -1
1 1 -1 -1
-1 1 1 -1
-1 -1 1 1
3 4
2 -3 4 -1
1 2 -4 -7
1 1 -7 2
4 3
1 -1 1
-2 4 5
2 -3 2
6 -5 7
1 1
1
2 2
-1 -1
-1 -2

输出

复制 
8
8
20
1
-2