看到相邻格子都+1的操作一下就想到黑白染色了
相邻格子都+1说明不管怎么弄，黑格子的总和和白格子总和的差总是定值
这里首先要注意，最后不一定变成的是所有元素中的最大值，可能比它大
比如 1 2 2
2 1 0 这里最后可以全变成3
所以做题的时候下结论一定要小心，我们不妨设最后都变成了x，c1,c2表示黑白格子个数，s1,s2分别表示原来黑白格子元素和
则x*c1-s1=x*c2-s2
则(c1-c2)*x=s1-s2
如果棋盘格子数为奇数，则，最后一定变成(s1-s2)/(c1-c2)，我们只要验证这个即可
否则，当s1≠s2则无解
等于的话就有许多解，随着x的增大显然操作次数增多，所以我们二分x判定
如何判定呢？
我们将s连黑点，白点连t，流量是x-初始值
对相邻黑白点连inf的边，表示这两个格子可以共同+1
最后我们只要判断是否满流即可
const inf=int64() shl ;
dx:array[..] of longint=(,,-,);
dy:array[..] of longint=(,-,,); type node=record
next,po:longint;
flow:int64;
end; var e:array[..] of node;
p,cur,pre,numh,h:array[..] of longint;
d:array[..] of int64;
num:array[..,..] of longint;
a:array[..,..] of int64;
test,t,i,n,m,j,k,len:longint;
ans,mx,s1,s2,l,r,mid:int64; function min(a,b:int64):int64;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint;f:int64);
begin
inc(len);
e[len].po:=y;
e[len].flow:=f;
e[len].next:=p[x];
p[x]:=len;
end; procedure build(x,y:longint;f:int64);
begin
add(x,y,f);
add(y,x,);
end; function sap:int64;
var u,i,j,tmp,q:longint;
neck:int64; begin
fillchar(h,sizeof(h),);
fillchar(numh,sizeof(numh),);
for i:= to t do
cur[i]:=p[i];
neck:=inf;
numh[]:=t+;
u:=;
sap:=;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=e[i].po;
if (e[i].flow>) and (h[u]=h[j]+) then
begin
neck:=min(neck,e[i].flow);
cur[u]:=i;
pre[j]:=u;
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(e[j].flow,neck);
inc(e[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=e[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=e[i].po;
if (e[i].flow>) and (h[j]<tmp) then
begin
tmp:=h[j];
q:=i;
end;
i:=e[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; function check(w:int64):boolean;
var i,j,x,y:longint;
s:int64;
begin
len:=-;
s:=;
fillchar(p,sizeof(p),);
for i:= to n do
for j:= to m do
if (i+j) mod = then build(num[i,j],t,w-a[i,j])
else begin
build(,num[i,j],w-a[i,j]);
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if num[x,y]> then build(num[i,j],num[x,y],inf);
end;
s:=s+w-a[i,j];
end; if sap<>s then exit(false)
else begin
ans:=s;
exit(true);
end;
end; begin
readln(test);
while test> do
begin
dec(test);
readln(n,m);
fillchar(num,sizeof(num),);
s1:=;
s2:=;
k:=;
mx:=;
for i:= to n do
for j:= to m do
begin
read(a[i,j]);
inc(k);
num[i,j]:=k;
if (i+j) mod = then s1:=s1+a[i,j]
else s2:=s2+a[i,j];
if a[i,j]>mx then mx:=a[i,j];
end;
t:=n*m+;
ans:=-;
if n*m mod = then
begin
if (mx<=s1-s2) and check(s1-s2) then writeln(ans)
else writeln(-);
end
else begin
if s1<>s2 then writeln(-)
else begin
l:=mx;
r:=int64() shl ;
while l<=r do
begin
mid:=(l+r) shr ;
if check(mid) then r:=mid-
else l:=mid+;
end;
writeln(ans);
end;
end;
end;
end.