问题 F: Intersecting Intervals

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.