Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。

  1 const oo=1<<50;
  2       dx:array[1..4]of longint=(-1,1,0,0);
  3       dy:array[1..4]of longint=(0,0,-1,1);
  4 var head,gap,dis:array[0..2000]of longint;
  5     vet,next,fan:array[1..200000]of longint;
  6     len:array[1..200000]of int64;
  7     num,a:array[1..40,1..40]of longint;
  8     n,m,i,j,tot,k1,k2,s,source,src,cas,v,mx:longint;
  9     l,r,mid,last,s1,s2,k:int64;
 10 
 11 procedure add(a,b:longint;c:int64);
 12 begin
 13  inc(tot);
 14  next[tot]:=head[a];
 15  vet[tot]:=b;
 16  len[tot]:=c;
 17  head[a]:=tot;
 18 
 19  inc(tot);
 20  next[tot]:=head[b];
 21  vet[tot]:=a;
 22  len[tot]:=0;
 23  head[b]:=tot;
 24 end;
 25 
 26 function min(x,y:int64):int64;
 27 begin
 28  if x<y then exit(x);
 29  exit(y);
 30 end;
 31 
 32 function dfs(u:longint;aug:int64):int64;
 33 var e,v,val:longint;
 34     flow,t:int64;
 35 begin
 36  if u=src then exit(aug);
 37  e:=head[u]; val:=s-1; flow:=0;
 38  while e<>0 do
 39  begin
 40   v:=vet[e];
 41   if len[e]>0 then
 42   begin
 43    if dis[u]=dis[v]+1 then
 44    begin
 45     t:=dfs(v,min(len[e],aug-flow));
 46     len[e]:=len[e]-t;
 47     len[fan[e]]:=len[fan[e]]+t;
 48     flow:=flow+t;
 49     if dis[source]>=s then exit(flow);
 50     if aug=flow then break;
 51    end;
 52    val:=min(val,dis[v]);
 53   end;
 54   e:=next[e];
 55  end;
 56  if flow=0 then
 57  begin
 58   dec(gap[dis[u]]);
 59   if gap[dis[u]]=0 then dis[source]:=s;
 60   dis[u]:=val+1;
 61   inc(gap[dis[u]]);
 62  end;
 63  exit(flow);
 64 end;
 65 
 66 function maxflow:int64;
 67 var ans:int64;
 68 begin
 69  fillchar(gap,sizeof(gap),0);
 70  fillchar(dis,sizeof(dis),0);
 71  gap[0]:=s; ans:=0;
 72  while dis[source]<s do ans:=ans+dfs(source,oo);
 73  exit(ans);
 74 end;
 75 
 76 function max(x,y:longint):longint;
 77 begin
 78  if x>y then exit(x);
 79  exit(y);
 80 end;
 81 
 82 function isok(k:int64):boolean;
 83 begin
 84  if k*k1-s1=maxflow then exit(true);
 85  exit(false);
 86 end;
 87 
 88 procedure build(k:int64);
 89 var i,j,l,x,y:longint;
 90 begin
 91  fillchar(head,sizeof(head),0); tot:=0;
 92  for i:=1 to n do
 93   for j:=1 to m do
 94    if (i+j) mod 2=0 then
 95    begin
 96     for l:=1 to 4 do
 97     begin
 98      x:=i+dx[l]; y:=j+dy[l];
 99      if (x>0)and(x<=n)and(y>0)and(y<=m) then add(num[i,j],num[x,y],oo);
100     end;
101    end;
102 
103  for i:=1 to n do
104   for j:=1 to m do
105    if (i+j) mod 2=0 then add(source,num[i,j],k-a[i,j])
106     else add(num[i,j],src,k-a[i,j]);
107 end;
108 
109 begin
110  assign(input,‘bzoj2756.in‘); reset(input);
111  assign(output,‘bzoj2756.out‘); rewrite(output);
112  read(cas);
113  for i:=1 to 200000 do
114   if i mod 2=1 then fan[i]:=i+1
115    else fan[i]:=i-1;
116 // for i:=1 to 40 do
117  // for j:=1 to 40 do num[i,j]:=(i-1)*40+j;
118  for v:=1 to cas do
119  begin
120   read(n,m);
121   s1:=0; s2:=0; k1:=0; k2:=0; mx:=-maxlongint;
122   for i:=1 to n do
123    for j:=1 to m do
124    begin
125     read(a[i,j]);
126     if (i+j) mod 2=0 then begin inc(k1); s1:=s1+a[i,j]; end
127      else begin inc(k2); s2:=s2+a[i,j]; end;
128     mx:=max(mx,a[i,j]); num[i,j]:=(i-1)*m+j;
129    end;
130   s:=n*m+2; source:=n*m+1; src:=n*m+2;
131   if k1<>k2 then
132   begin
133    k:=(s1-s2) div (k1-k2);
134    if k<mx then writeln(-1)
135     else
136     begin
137      build(k);
138      if isok(k) then writeln(k*k1-s1)
139       else writeln(-1);
140     end;
141   end
142    else
143    begin
144     if s1<>s2 then writeln(-1)
145      else
146      begin
147       l:=mx; r:=oo; last:=oo;
148       while l<=r do
149       begin
150        mid:=(l+r)>>1;
151        build(mid);
152        if isok(mid) then begin last:=mid; r:=mid-1; end
153         else l:=mid+1;
154       end;
155       writeln(last*k1-s1);
156      end;
157    end;
158 
159 
160  end;
161 
162  close(input);
163  close(output);
164 end.