Pak Chanek has a friend who runs a drink stall in a canteen. His friend will sell drinks for 𝑛 days, numbered from day 1 to day 𝑛. There are also 𝑚 types of drinks, numbered from 1 to 𝑚.

The profit gained from selling a drink on a particular day can vary. On day 𝑖, the projected profit from selling drink of type 𝑗 is 𝐴𝑖,𝑗. Note that 𝐴𝑖,𝑗 can be negative, meaning that selling the drink would actually incur a loss.

Pak Chanek wants to help his friend plan the sales over the 𝑛 days. On day 𝑖, Pak Chanek must choose to sell at least one type of drink. Furthermore, the types of drinks sold on a single day must form a subarray. In other words, in each day, Pak Chanek will select 𝑖 and 𝑗 such that 1≤𝑖≤𝑗≤𝑚. Then all types of drinks between 𝑖 and 𝑗 (inclusive) will be sold.

However, to ensure that customers from the previous day keep returning, the selection of drink types sold on day 𝑖 (𝑖>1) must meet the following conditions:

At least one drink type sold on day 𝑖 must also have been sold on day 𝑖−1.
At least one drink type sold on day 𝑖 must not have been sold on day 𝑖−1.
The daily profit is the sum of the profits from all drink types sold on that day. The total profit from the sales plan is the sum of the profits over 𝑛 days. What is the maximum total profit that can be achieved if Pak Chanek plans the sales optimally?

Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤1000). The description of the test cases follows.

The first line of each test case contains two integers 𝑛 and 𝑚 (1≤𝑛≤2⋅105; 3≤𝑚≤2⋅105; 𝑛⋅𝑚≤2⋅105) — the number of rows and columns in a grid.

The next 𝑛 lines of each test case contain 𝑚 integers each, where the 𝑖-th line contains the integers 𝐴𝑖,1𝐴𝑖,2,…,𝐴𝑖,𝑚 (−109≤𝐴𝑖,𝑗≤109) — project profits of each drink type on the 𝑖-th day.

It is guaranteed that the sum of 𝑛⋅𝑚 over all test cases does not exceed 2⋅105.

Output
For each test case, output a single integer: the maximum profit that Pak Chanek can achieve.

Example
inputCopy
1
3 6
79 20 49 5 -1000 500
-105 9 109 24 -98 -499
14 47 12 39 23 50
outputCopy
475
Note
Here is Pak Chanek's optimal plan:

		
On day 1, Pak Chanek sells drink types 1 to 3. Generating a profit of 79+20+49=148.
On day 2, Pak Chanek sells drink types 2 to 4. Generating a profit of 9+109+24=142
On day 3, Pak Chanek sells drink types 1 to 6. Generating a profit of 185.
So, the total profit of Pak Chanek's plan is 148+142+185=475.
The following solution return wrong answer expected 475 but return 230. #include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

#define ll long long

using namespace std;

void solve() {
  int n, m; cin >> n >> m;
  vector<vector<int>> A(n, vector<int>(m));
  for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> A[i][j];
  ll total =0;
  int prevL, prevR;
  // Day 1
  ll current_sum =0;
  ll max_sum = LLONG_MIN;
  int start=0, bestL=0, bestR=0;
  for(int j=0;j<m;j++){
    if(current_sum <=0){
      current_sum = A[0][j];
      start = j;
    }
    else{
      current_sum += A[0][j];
    }
    if(current_sum > max_sum){
      max_sum = current_sum;
      bestL = start;
      bestR = j;
    }
  }
  total += max_sum;
  prevL = bestL;
  prevR = bestR;
  // Days 2 to n
  for(int i=1;i<n;i++){
    max_sum = LLONG_MIN;
    current_sum =0;
    start=0;
    int bestLi=0, bestRi=0;
    bool has_overlap = false, has_non_overlap = false;
    for(int j=0;j<m;j++){
      if(current_sum <=0){
        current_sum = A[i][j];
        start = j;
        has_overlap = (j >= prevL && j <= prevR) ? true : false;
        has_non_overlap = !(j >= prevL && j <= prevR) ? true : false;
      }
      else{
        current_sum += A[i][j];
        if(j >= prevL && j <= prevR) has_overlap = true;
        else has_non_overlap = true;
      }
      if(has_overlap && has_non_overlap){
        if(current_sum > max_sum){
          max_sum = current_sum;
          bestLi = start;
          bestRi = j;
        }
      }
      if(current_sum <0){
        current_sum =0;
        has_overlap = false;
        has_non_overlap = false;
      }
    }
    total += max_sum;
    prevL = bestLi;
    prevR = bestRi;
  }
  cout << total << "\n";
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin >> t;
  while(t--) solve();
}