#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <cassert>#include <queue>#define ll long long#define vi vector <int>#define pii pair <int,int>#define FOR(i, a, b) for (i = (a); i <= (b); i++)#define REP(i, a) for (i = 0; i < (a); i++)#define ALL(v) (v).begin(), (v).end()#define SET(a, x) memset((a), (x), sizeof(a))#define SZ(a) ((int)(a).size())#define CL(a) ((a).clear())#define SORT(x) sort(ALL(x))#define mp make_pair#define pb push_back#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))using namespace std;#define NN 102int dp[NN][NN],G[NN][NN][NN],Left[NN][NN],Right[NN][NN],A[NN][NN],Cons[NN][NN];#define INF 1000000000int R,C;void go( int r , int lc ){ if(dp[r][lc]!=-1)return; if(r==R) { if(lc!=C-1)dp[r][lc]=-INF; else dp[r][lc]=0; return; } dp[r][lc]=-INF; int i,gain,v; for(i=0;i<C;i++) { gain=G[r][lc][i]; if(i<lc) { gain+=Left[r][i]; gain+=Right[r][lc]; } else { gain+=Left[r][lc]; gain+=Right[r][i]; }go(r+1,i); v=dp[r+1][i]+gain; dp[r][lc]=MAX( dp[r][lc] , v ); } return ;}int main(){ int T,i,j,k; scanf("%d",&T); while(T--) { scanf("%d%d",&R,&C); REP(i,R)REP(j,C)scanf("%d",&A[i][j]); REP(i,R) { REP(j,C) { if(!j)Cons[i][j]=A[i][j]; else Cons[i][j]=Cons[i][j-1]+A[i][j]; } } REP(i,R) { REP(j,C) { REP(k,C) { if(k<j)G[i][j][k]=G[i][k][j]; else { G[i][j][k]=Cons[i][k]-Cons[i][j]+A[i][j]; } } } } int tot; REP(i,R) { REP(j,C) { Left[i][j]=0; tot=0; for(k=j-1;k>=0;k--) { tot+=(-abs(A[i][k+1])); tot+=A[i][k]; Left[i][j]=MAX(Left[i][j],tot); } } } REP(i,R) { REP(j,C) { Right[i][j]=0; tot=0; for(k=j+1;k<C;k++) { tot+=(-abs(A[i][k-1])); tot+=A[i][k]; Right[i][j]=MAX(Right[i][j],tot); } } } SET(dp,-1); go( 0,0 ); printf("%dn",dp[0][0]); } return 0;}
